+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** یار عادت دارد اول هر نامه‌ای که به دستش می‌رسد را پاک کند(نه لزومن نامه‌ی شیرین عسل)!! و برای این کار یک ماشین ساخته است. این ماشین به این صورت کار می‌کند که با وضعیت $1$ شروع می‌کند و در هر مرحله با توجه به حرف اول از نامه‌ای که باقی مانده است و وضعیت فعلی دستگاه و قوانینی که یار برای ماشین تعریف کرده است یکی از کارهای زیر را انجام می‌دهد. 1. اگر ماشین در وضعیت $v$ باشد و حرف اول نامه‌ی باقی‌مانده $c$ باشد و قانونی مانند `v u c` وجود داشته باشد حرف اول نامه پاک می‌شود و وضعیت ماشین به $u$ تغییر می‌کند ($v$ و $u$ اعداد طبیعی و نمایانگر شماره وضعیت هستند و $c$ یک حرف کوچک انگلیسی است). 2. اگر هیچ قانونی مانند `v u c` وجود نداشته باشد وجود نداشته باشد کار ماشین به پایان می‌رسد و نامه‌ی باقی مانده را به یار تحویل می‌دهد.  # ورودی در سطر اول ورودی دو عدد طبیعی $n$‌ و $m$ آمده است که به ترتیب نمایانگر تعداد وضعیت‌های ماشین و تعداد قوانین است. در خط بعدی رشته‌ی $s$ شامل حروف کوچک انگلیسی آمده است که نمایانگر متن نامه است. سپس در $m$ ‌خط بعدی در هر خط توضیح یکی از قوانین به صورت `v u c` آمده است. $$ 1 \le n \le 1\ 000 $$ $$ 1 \le m \le 26\ 000 $$ $$ 1 \le |s| \le 1\ 000 $$ $$ 1 \le v , u \le n $$ تضمین می‌شود هیچ دو قانونی با $v$ و $c$ یکسان وجود ندارند. # خروجی در تنها سطر خروجی نامه‌ی باقی‌مانده را چاپ کنید و اگر تمام نامه پاک شده بود $-1$ را چاپ کنید. # مثال ## ورودی نمونه ۱ شکل سمت راست ``` 2 2 ababbarbari 1 2 a 2 1 b ``` ## خروجی نمونه ۱ ``` barbari ``` ## ورودی نمونه ۲ شکل سمت چپ ``` 3 4 abcadc 1 2 a 2 3 b 2 3 d 3 1 c ``` ## خروجی نمونه ۲ ``` -1 ```

حل سؤال در بانک سؤالات