evo

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 $w_R$ şirul obţinut prin oglindirea lui $w$. De exemplu pentru $w = aaagatat$, $w_R = tatagaaa$.
3. Hairpin. Pentru un şir de simboluri $w$, care poate fi descompus în patru subşiruri $w_1 w_2 w_3 w_4$ (unele dintre cele patru siruri pot fi vide) prin operaţia hairpin se obţine: $w_1 w_2 w_3 w_4 c(w_1)R$, dacă $w_2 = c(w_4)R$ şi lungimea lui $w_2$ este mai mare sau egală cu $1$, sau $c(w_4) R w_1 w_2 w_3 w_4$, dacă $w_1 = c(w_3)R$ şi lungimea lui $w_1$ 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 şi precizări

• $0 < n < 5$, $0 < m < 1 \ 001$
• 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 $16 \ 001$. Lungimea fiecărui şir de analizat este mai mică decât $4 \ 001$.
• În $55\%$ din teste lungimea maximă a unui şir de analizat este $700$.

Exemplu

evo.in

2
acgtcg
gaaaat
4
gaaaat
gaaaatcc
gaaaattc
cgacgtcgtcg

evo.out

da 
nu
da
da

Explicație

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 $w_1 = ga$, $w_2 = a$, $w_3 = aa$, $w_4 = 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 $w_1 = ac$, $w_2$ = şir vid, $w_3 = gt$, $w_4 = cg$, operaţia de hairpin adăugând $c(w_4)R$ la începutul şirului, şi apoi din cgacgtcg obţinem cgacgtcgtcg pentru $w_1 = cga$, $w_2 = c$, $w_3 = gtc$ şi $w_4 = g$, operaţia de hairpin adăugând $c(w_1)R$ la sfârşitul şirului.