Рівняння над словами
Вам дано слово T і шаблон P. Ви хочете перевірити, чи можна видалити деякі букви з T, щоб з решти символів утворити P. Наприклад, слово programming можна частково видалити, щоб отримати pong, program або roaming (але не map, оскільки букви повинні залишатися в тому ж порядку). Обидва слова складаються лише з малих літер англійського алфавіту.
Є лише одна складність: текст T кодується системою рівнянь. У рівняннях використовуються спеціальні символи (кожен символ позначається словом з великих літер), кожен з яких кодує певне слово в алфавіті {a, ..., z}. Кожне рівняння має одну з наступних форм:
A = слово над алфавітом {a,...,z}
або
A = B + C
де A, B, C можуть бути будь-якими символами, а символ + означає конкатенацію слів. Система є:
однозначною – для фіксованого символу A існує рівно одне рівняння з A в лівій частині;
ациклічною – якщо ви починаєте з будь-якого символу A, робите підстановки відповідно до рівнянь, і ніколи не зможете отримати вираз, що містить A знову.
Така система завжди має єдине розв'язання. Наприклад, у системі:
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
символ START кодує слово goodtimesbadtimes.
Маючи одне слово P як шаблон, систему рівнянь і один конкретний початковий символ S цієї системи, визначте, чи присутній шаблон P у слові, закодованому S.
Вхідні дані
Перший рядок містить кількість тестів t. Опис тестів наведено нижче:
Кожен тест починається з рядка, що містить одне ціле число k (1 ≤ k ≤ 500) - кількість рівнянь. Наступні k рядків містять рівняння. Кожне з них має одну з двох форм, зазначених в умові задачі, з пробілами, що розділяють слова, знаками плюс і знаками рівнянь. Кожне слово (включаючи імена символів) має довжину не менше одного і не більше п'яти символів.
Наступний рядок містить один спеціальний символ (слово великими літерами), а заключний рядок містить непорожнє слово, що містить не більше 2000 малих літер. Це початковий символ і шаблон для пошуку відповідно.
Вихідні дані
Для кожного тесту виведіть відповідь в окремому рядку: YES, якщо шаблон присутній у заданому слові, і NO в іншому випадку.