• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

یار عادت دارد اول هر نامه‌ای که به دستش می‌رسد را پاک کند(نه لزومن نامه‌ی شیرین عسل)!! و برای این کار یک ماشین ساخته است.

این ماشین به این صورت کار می‌کند که با وضعیت $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

شکل سمت چپ