Populatia planetei Algorithm este amenintata de virusi extrem de periculosi. Din fericire biologii de pe planeta au reusit sa analizeze structura genetica a virusilor si sa obtina o descriere completa a modului lor de evolutie. Astfel, nucleotidele ce compun structura ADN a unui virus pot fi notate cu cifrele de la 0 la 9 (0,1,2,3,4,5,6,7,8,9). Dintre acestea, unele sunt adulte si nu mai pot evolua (nu mai pot fi transformate), pe cand altele sunt inca tinere si mai pot evolua (mai pot fi transformate in alte nucleotide). Structura virusului este reprezentata de un sir de cifre (nucleotide) citit de la stanga catre dreapta.

Evolutia este o succesiune de pasi, fiecare dintre ei putand fi descris formal astfel: o nucleotida tinara se transforma in (este inlocuita de) alte doua nucleotide oarecare, sau in (de) exact o nucleotida adulta. Aceste transformari sunt determinate de niste reguli cunoscute de forma: “C se transforma in X Y” sau “C se transforma in X”; aceste reguli se pot traduce astfel: in sirul de cifre care reprezinta structura virusului, nucleotida C este stearsa, iar in locul sau sunt introduse nucleotidele XY (in aceasta ordine, X la stanga lui Y), respectiv de nucleotida X. S-a observat ca un sir de cifre reprezinta structura un virus daca si numai daca el poate fi obtinut prin aplicarea suucesiva a regulilor de evolutie asupra nucleotidei 0; orice alt sir reprezinta un alt organism. De asemenea este cunoscut faptul ca un virus a carui structura ADN contine doar nucleotide adulte este mai putin periculos ca un virus a carui structura ADN contine si nucleotide tinere.

Cerinta

Dandu-se lista nucleotidelor considerate adulte, regulile de evolutie si un sir care reprezinta structura ADN a unui organism, se cere sa se spuna daca acel sir poate reprezenta structura unui virus, caz in care trebuie precizat daca acest virus este format doar din nucleotide adulte sau daca are in componenta si nucleotide tinere.

Date de intrare

Fisierul de intrare contine pe prima linie un numar natural m care reprezinta numarul de nucleotide tinere. Pe cea de a doua linie se afla un sir de m cifre separate prin spatiu c₁, c₂, ..., c_m care reprezinta cifrele care identifica nucleotidele tinere. Pe linia a treia se afla un numar natural n reprezentand numarul de reguli de evolutie ce urmeaza a fi descrise in fisier. Pe fiecare dintre urmatoarele n linii se afla cate un triplet sub forma
c₁₁ c₁₂ c₁₃
c₂₁ c₂₂ c₂₃
...
c_n1 c_n2 c_n3

Daca regula j este de primul tip (i.e. o nucleotida tanara se poate transforma in alte doua nucleotide oarecare) atunci toate cele trei valori c_j1, c_j2 si c_j3 sunt cifre care reprezinta nucleotide, cu semnificatia ca nucleotida c_j1 se transforma in nucleotidele c_j2 si c_j3. Daca regula j este de al doilea tip (i.e. o nucleotida tinara se poate transforma in exact o nucleotida adulta) atunci cj1 si c_j2 sunt cifre care reprezinta nucleotide (cu semnificatia ca nucleotida c_j1 se transforma in nucleotida adulta c_j2), iar c_j3 este –1. Cele trei numere din fiecare triplet sunt separate prin spatiu.

Pe urmatoarea linie in fisierul de intrare se afla un numar natural k care reprezinta numarul de organisme a caror structura trebuie analizata. Pe urmatoarele k linii se afla k siruri de cifre, fiecare pe o linie noua; cele k siruri reprezinta structura a k organisme.

Date de iesire

Pentru fiecare dintre cele k siruri din fisierul de intrare, trebuie sa se afiseze, pe rand nou mesajul not a virus (in cazul in care sirul respectiv nu reprezinta structura unui virus), an adult virus (in cazul in care sirul respectiv reprezinta structura unui virus adult), a young virus (in cazul in care sirul respectiv reprezinta structura unui virus ce contine nucleotide tinere).

Restrictii si precizari

• 1 <= m <= 9
• 1 <= n <= 10
• 1 <= k <= 20
• Lungimea fiecarui sir dintre cele k este mai mica de 100 de cifre.
• Nu este obligatoriu ca structura ADN a unui organism sa contina toate cele 10 cifre cu care pot fi reprezentate nucleotidele.
• Datele sunt considerate valide.

Exemplu

prep. Florin Manea
Facultatea de Matematica si Informatica, Universitatea din Bucuresti
Contact: flmanea@gmail.com