- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یار عادت دارد اول هر نامهای که به دستش میرسد را پاک کند(نه لزومن نامهی شیرین عسل)!! و برای این کار یک ماشین ساخته است.
این ماشین به این صورت کار میکند که با وضعیت \(1\) شروع میکند و در هر مرحله با توجه به حرف اول از نامهای که باقی مانده است و وضعیت فعلی دستگاه و قوانینی که یار برای ماشین تعریف کرده است یکی از کارهای زیر را انجام میدهد.
- اگر ماشین در وضعیت \(v\) باشد و حرف اول نامهی باقیمانده \(c\) باشد و قانونی مانند
v u cوجود داشته باشد حرف اول نامه پاک میشود و وضعیت ماشین به \(u\) تغییر میکند (\(v\) و \(u\) اعداد طبیعی و نمایانگر شماره وضعیت هستند و \(c\) یک حرف کوچک انگلیسی است). - اگر هیچ قانونی مانند
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
شکل سمت چپ