3. *Hairpin*. Pentru un sir de simboluri $w$, care poate fi descompus in patru subsiruri $w{~1~}w{~2~}w{~3~}w{~4~}$ (unele dintre cele patru siruri pot fi vide) prin operatia hairpin se obtine: $w{~1~}w{~2~}w{~3~}w{~4~}c(w{~1~})^R^$, daca $w{~2~}=c(w{~4~})^R^$ si lungimea lui $w{~2~}$ este mai mare sau egala cu $1$, sau $c(w{~4~})^R^w{~1~}w{~2~}w{~3~}w{~4~}$, daca $w{~1~}=c(w{~3~})^R^$ si lungimea lui $w{~1~}$ este mai mare sau egala cu $1$.
Daca ambele conditii sunt verificate, oricare dintre cele doua siruri se poate obtine.

In gradina Acolor a fost descoperita o specie de omizi cu simt artistic. Informatia genetica a omizilor este codificata printr-o multime $S$ formata din $n$ siruri de simboluri din multimea ${a, c, g, t}$. Multimea $S$ este denumita multime initiala. In evolutia omizilor, informatia genetica initială a suferit o serie de modificari. Pentru omizi, toate aceste modificari pot fi descrise prin aplicarea operatiei hairpin de un numar arbitrar de ori asupra sirurilor din multimea initiala $S$.

In gradina Acolor a fost descoperita o specie de omizi cu simt artistic. Informatia genetica a omizilor este codificata printr-o multime $S$ formata din $n$ siruri de simboluri din multimea ${a, c, g, t}$. Multimea $S$ este denumita multime initiala. In evolutia omizilor, informatia genetica initiala a suferit o serie de modificari. Pentru omizi, toate aceste modificari pot fi descrise prin aplicarea operatiei hairpin de un numar arbitrar de ori asupra sirurilor din multimea initiala $S$.

Date fiind cele $n$ siruri din multimea initiala $S$ si o succesiune de $m$ siruri de simboluri, sa se decida care dintre cele $m$ siruri poate reprezenta codul genetic al unei omizi, cod obtinut prin aplicarea unor operatii hairpin.

h2. Date de iesire

Fisierul de iesire $evo.out$ va contine $m$ linii, cate una pentru fiecare sir de analizat. Pe linia $i$ se va scrie cuvantul $da$, daca al $i$-lea sir dintre cele $m$ siruri de analizat poate fi codul genetic al unei omizi, respectiv cuvantul $nu$, în caz contrar.

Fisierul de iesire $evo.out$ va contine $m$ linii, cate una pentru fiecare sir de analizat. Pe linia $i$ se va scrie cuvantul $da$, daca al $i$-lea sir dintre cele $m$ siruri de analizat poate fi codul genetic al unei omizi, respectiv cuvantul $nu$, in caz contrar.

h2. Restrictii