== include(page="template/taskheader" task_id="nfa") ==

Poveste şi cerinţă...

Se da un NFA (nondeterministic finite automata) format N stari, M tranzitii si K stari finale, fiecare tranzitie presupunand o litera mica din alfabetul limbii engleze si Q cuvinte.
Afisati pentru fiecare cuvant 1 daca automatul il contine si 0, altfel.

h2. Date de intrare

Fişierul de intrare $nfa.in$ ...

Fişierul de intrare $nfa.in$ va contine pe prima linie 3 numere N, M si K (cu semnificatia din enunt), iar pe a 2-a linie un numar S, reprezentand starea initiala. Pe a 3-a linie se vor afla K numere reprezentand starile finale. Pe urmatoarele M linii se gasesc cate 2 numere si un caracter reprezentand tranzitia dintre 2 stari. Pe urmatoare linie se va afla un numar Q, urmatoarele Q linii vor contine cate 1 sir de caractere.

h2. Date de ieşire

În fişierul de ieşire $nfa.out$ ...

În fişierul de ieşire $nfa.out$ se vor afla Q linii, pe fiecare dintre ele aflandu-se un numar 0 sau 1.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$ ; $1 ≤ N ≤ 400.000$
* Pentru 50 de puncte $1 ≤ N ≤ 1.000$ ; $1 ≤ N ≤ 4.000$
* NFA-ul dat are o singura stare initiala

h2. Exemplu