Problem
Esok Belvita membuka kedai rotinya, tetapi dia masih belum menyediakan papan tanda untuk penubuhannya.
Belvita mempunyai n set tablet di dalam almarinya, setiap satunya mengandungi 3 tablet yang sama mengandungi tepat dua huruf Latin huruf kecil.
Belvite tidak kisah apa nama kedai rotinya, tetapi dia mahu nama akhir mengandungi subrentetan s, yang juga terdiri daripada dua huruf Latin huruf kecil.
Bantu Belvita melihat sama ada anda boleh memilih beberapa tablet yang tersedia dan menggunakannya untuk membuat nama kedai roti supaya ia mengandungi subrentetan yang diperlukan.
Input:
Baris pertama mengandungi dua huruf Latin huruf kecil - rentetan s yang Belvita ingin lihat dalam nama kedai roti.
Baris kedua mengandungi satu integer n (1 <= n <= 100) - bilangan set plak dalam almari.
N baris seterusnya mengandungi dua huruf Latin huruf kecil setiap satu menerangkan inskripsi pada tablet dalam set.
Output:
Cetak "YA" jika Belvita boleh memilih beberapa tablet supaya perkataan yang terhasil mengandungi subrentetan s dan "TIDAK" sebaliknya.
Contoh:
| Input |
Output |
ya
4
ah
oy
kepada
ha |
YA |
hp
2
ht
tp |
TIDAK |
ah
1
ha |
YA |
Penjelasan:
Dalam contoh pertama, anda boleh menggunakan set ketiga, kedua dan pertama dengan membuat perkataan "tooyah" yang mengandungi subrentetan "ya".
Dalam contoh kedua, dapatkan perkataan dengan subrentetan "hp" tidak mungkin.
Dalam contoh ketiga, anda boleh menggunakan dua daripada tiga tablet daripada set pertama, menjadikan perkataan "haha" di mana terdapat subrentetan "ah".