+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
یار عادت دارد اول هر نامه‌ای که به دستش می‌رسد را پاک کند(نه لزومن نامه‌ی شیرین عسل)!! و برای این کار یک ماشین ساخته است.
این ماشین به این صورت کار می‌کند که با وضعیت $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
```
شکل سمت چپ