Sözlər üzərində tənliklər
Sizə T mətni və P şablonu verilib. Siz T mətnindən bəzi hərfləri silərək qalan simvollarla P əldə edə biləcəyinizi yoxlamaq istəyirsiniz. Məsələn, programming sözünü qismən silərək pong, program və ya roaming (amma map deyil, çünki hərflər eyni ardıcıllıqda qalmalıdır) əldə etmək olar. Hər iki söz yalnız kiçik ingilis əlifbası hərflərindən ibarətdir.
Burada yalnız bir çətinlik var: T mətni tənliklər sistemi ilə kodlanır. Tənliklərdə xüsusi simvollar istifadə olunur (hər bir simvol böyük hərflərlə yazılmış bir sözlə təmsil olunur) və bu simvollar əlifbada {a, ..., z} olan bir sözü kodlayır. Hər bir tənlik aşağıdakı formalardan birinə malikdir:
A = əlifba üzərində söz {a,...,z}
və ya
A = B + C
burada A, B, C istənilən simvol ola bilər və + simvolu sözlərin birləşdirilməsini ifadə edir. Sistem:
birmənalıdır – müəyyən bir A simvolu üçün sol tərəfdə A olan dəqiq bir tənlik mövcuddur;
dövrü olmayan – hər hansı bir A simvolundan başlayaraq tənliklərə uyğun əvəzləmələr etdikdə, heç vaxt yenidən A simvolunu ehtiva edən ifadə əldə edə bilməzsiniz.
Belə bir sistem həmişə yeganə həllə malikdir. Məsələn, sistemdə:
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
START simvolu goodtimesbadtimes sözünü kodlayır.
Bir P sözü şablon olaraq, tənliklər sistemini və bu sistemin bir konkret başlanğıc simvolunu S nəzərə alaraq, P şablonunun S ilə kodlanmış sözdə olub-olmadığını müəyyən edin.
Giriş Məlumatları
Birinci sətir testlərin sayı t-ni ehtiva edir. Testlərin təsvirləri aşağıda verilmişdir:
Hər bir test k tam ədədi (1 ≤ k ≤ 500) ehtiva edən bir sətirlə başlayır - tənliklərin sayı. Növbəti k sətir tənlikləri ehtiva edir. Onların hər biri məsələnin şərtində göstərilən iki formadan birinə malikdir, sözləri, plus işarələrini və bərabərlik işarələrini ayıran boşluqlarla. Hər bir sözün (simvol adları daxil olmaqla) uzunluğu ən azı bir və ən çox beş simvoldur.
Növbəti sətir bir xüsusi simvolu (böyük hərflərlə yazılmış söz) ehtiva edir və sonuncu sətir ən çox 2000 kiçik hərfdən ibarət olan boş olmayan bir sözü ehtiva edir. Bu, müvafiq olaraq başlanğıc simvolu və axtarış üçün şablondur.
Çıxış Məlumatları
Hər bir test üçün cavabı ayrı sətirdə verin: əgər şablon verilmiş sözdə varsa YES, əks halda NO.