Este binecunoscut faptul că informaţia genetică a unui organism poate fi codificată sub forma unui şir format din simboluri din mulţimea {g, a, t, c}. Pornind de la această codificare biologii au identificat 3 operaţii asupra şirurilor de simboluri, operaţii care pot modela evoluţia anumitor organisme.
1. Complementaritate. Simbolul a este complementarul lui t (şi reciproc), iar simbolul c este complementarul lui g (şi reciproc). Pentru un simbol x vom nota cu c(x) complementarul său. Prin extensie, dacă w este un şir de simboluri din mulţimea {a, c, g, t} notăm cu c(w) şirul obţinut prin complementarea simbolurilor lui w. De exemplu, pentru w=aaactg, avem c(w)=tttgac.
2. Oglindire. Vom nota prin wR şirul obţinut prin oglindirea lui w. De exemplu pentru w=aaagatat, wR=tatagaaa.
3. Hairpin. Pentru un şir de simboluri w, care poate fi descompus în patru subşiruri w1w2w3w4 (unele dintre cele patru siruri pot fi vide) prin operaţia hairpin se obţine: w1w2w3w4c(w1)R, dacă w2=c(w4)R şi lungimea lui w2 este mai mare sau egală cu 1, sau c(w4)Rw1w2w3w4, dacă w1=c(w3)R şi lungimea lui w1 este mai mare sau egală cu 1.
Dacă ambele condiţii sunt verificate, oricare dintre cele două şiruri se poate obţine.
În gradina Acolor a fost descoperită o specie de omizi cu simţ artistic. Informaţia genetică a omizilor este codificată printr-o mulţime S formată din n şiruri de simboluri din mulţimea {a, c, g, t}. Mulţimea S este denumită mulţime iniţială. În evoluţia omizilor, informaţia genetică iniţială a suferit o serie de modificări. Pentru omizi, toate aceste modificări pot fi descrise prin aplicarea operaţiei hairpin de un număr arbitrar de ori asupra şirurilor din mulţimea iniţială S.
Cerinţă
Date fiind cele n şiruri din mulţimea iniţială S şi o succesiune de m şiruri de simboluri, să se decidă care dintre cele m şiruri poate reprezenta codul genetic al unei omizi, cod obţinut prin aplicarea unor operaţii hairpin.
Date de intrare
Fişierul de intrare evo.in conţine n+m+2 linii. Pe prima linie este scris numărul natural n reprezentând numărul de numărul de şiruri din mulţimea iniţială S. Urmează n linii, pe fiecare linie fiind scris un şir din mulţimea S.
Pe linia n+2 este scris numărul natural m, reprezentând numărul de şiruri care trebuie să fie analizate. Pe următoarele m linii sunt scrise cele m şiruri care trebuie analizate, câte un şir pe o linie.
Date de ieşire
Fişierul de ieşire evo.out va conţine m linii, câte una pentru fiecare şir de analizat. Pe linia i se va scrie cuvântul da, dacă al i-lea şir dintre cele m şiruri de analizat poate fi codul genetic al unei omizi, respectiv cuvântul nu, în caz contrar.
Restricţii
0 < n < 5
0 < m < 1001
Lungimea unui şir din mulţimea iniţială S este mai mică decât 101.
Lungimea totală a şirurilor de analizat este mai mică decât 16001.
Lungimea fiecărui şir de analizat este mai mică decât 4001.
În 55% din teste lungimea maximă a unui şir de analizat este 700.
Primul şir de analizat este gaaaat. Acesta poate fi obţinut din gaaaat făra a aplica vreo operaţie hairpin.
Al doilea şir de analizat este gaaattc. Acesta nu poate fi obţinut prin aplicarea operaţiei hairpin asupra şirurilor acgtcg sau gaaaat.
Al treilea şir de analizat este gaaaattc. Acesta se obţine aplicând operaţia hairpin o singură dată asupra şirului gaaaat (considerând w1=ga, w2=a, w3=aa, w4=t).
Al patrulea şir de analizat este cgacgtcgtcg. Acesta se poate obţine din acgtcg aplicând de două ori operaţia hairpin (din acgtcg obţinem cgacgtcg pentru w1=ac, w2=şir vid, w3=gt, w4=cg, operaţia de hairpin adăugând c(w4)R la începutul şirului, şi apoi din cgacgtcg obţinem cgacgtcgtcg pentru w1=cga, w2=c, w3=gtc, w4=g, operaţia de hairpin adăugând c(w1)R la sfârşitul şirului.