Va era dor de Algorel? Iată ca au venit Stelele si e timpul sa apara iar în viaţa mondenă. De data asta concursul l-a prins uitându-se la un serial de desene animate. Cum tocmai a facut rost de un nou sezon ce are N episoade, Algorel ar vrea sa stie in ce ordine ar putea sa le vada. El stie de la un prieten o expresie care descrie cum se leaga episoadele intre ele. Expresia data respecta anumite reguli:

* intr-o expresie pot aparea numerele de la 1 la N precum si caracterele: {$(),#$}
* fiecare numar de la 1 la N apare o singura data in expresie iar fiecarui episod ii corespunde in mod unic un numar
* un grup de episoade poate fi un singur episod sau o subexpresie ce decrie relatii intre mai multe episoade
* $ge{~1~} , ge{~2~}$ - grupul de episoade $ge{~1~}$ trebuie vazut inainte de $ge{~2~}$
* $ge{~1~} # ge{~2~}$ - cele doua grupurile de episoade pot fi vazute in orice ordine dar fara sa se intercalaze
* $,$ are prioritate mai mare fata de $#$
* parantele pot aparea oriunde in expresie cu conditia sa fie bine inchise

* intr-o expresie pot aparea numerele de la 1 la N (fiecarui episod ii corespunde un numar) precum si caracterele: {$(),|$}
* o subexpresie a expresiei descrie relatii intre un anumit grup de episoade
* expresia ge_1_, ge_2_, ..., ge_k_ are semnificatia ca grupurile de episoade ge_1_, ge_2_, .., ge_k_ trebuie vazute neaparat in ordinea data; fiecare grup de episoade poate fi un singur episod sau o subexpresie ce decrie mai multe episoade
* expresia ge1 # ge2 # ... # gek spune ca grupurile de episoade care pot fi vazute in orice ordine dar fara sa se intercalaze

Pentru a va ajuta sa intelegeti regulile, Algorel va da si cateva exemple:
table(example). |_. expresie |_. ordini posibile |

| 1#2,3,4

| 1, (2 # 3), 4

| 1 2 3 4

  2 3 4 1 |
| ((3,(4#5),(1#(2,6))))
| 3 4 5 1 2 6
  3 4 5 2 6 1
  3 5 4 1 2 6
  3 5 4 2 6 1

  1 3 2 4 |
| ((3, 2), 1) # (4, 5) # (7, 6, 8)
| 3 2 1 4 5 7 6 8
  3 2 1 7 6 8 4 5
  4 5 3 2 1 7 6 8
  4 5 7 6 8 3 2 1
  7 6 8 3 2 1 4 5
  7 6 8 4 5 3 2 1

|

Acum Algorel are niste ordini posibile in care ar vrea sa vada episoadele pe care le-a gasit pe niste site-uri cu recomandari. El vrea sa stie care din aceste ordini corespund cu regulile descrise de expresie.

Acum Algorel are niste ordini posibile in care ar vrea sa vada episoadele pe care le-a gasit pe niste site-uri. El vrea sa stie care din aceste ordini se conformeaza regulilor expresiei si care nu.

h2. Date de intrare

Fişierul de intrare $episoade.in$ va contine pe prima linie expresia pe care Algorel o stie. Pe a doua linie se afla T - numarul de ordini pe care Algorel le-a gasit pe internet. Pe urmatoarele T linii se afla numerele 1 .. N (N este numarul maxim care apare in expresie) separate prin spatii ce descriu o anumita ordine a episoadelor.

Fişierul de intrare $episoade.in$ va contine pe prima linie expresia pe care Algorel o stie. Pe a doua linie se afla T - numarul de ordini pe care Algorel le-a gasit pe internet. Pe urmatoarele T linii se afla N numere (N este numarul maxim care apare in expresie) separate prin spatii care descriu fiecare cate o ordine.

h2. Date de ieşire

În fişierul de ieşire $episoade.out$ veti afisa T linii pentru fiecare din cele T ordini. Pe linia i veti scrie 1 daca ordinea i din fisierul de intrare este posibila conform expresiei sau 0 in caz contrar.

În fişierul de ieşire $episoade.out$ veti afisa T linii pentru fiecare din cele T ordini. Pe linia i veti scrie 1 daca ordinea i din fisierul de intrare este posibila conform expresiei sau 0 daca nu.

h2. Restricţii
* $1 ≤ N ≤ 500$
* Lungimea expresiei nu depaseste 2000 de caractere
* $1 ≤ T ≤ 30$

* Pentru 50% din teste $1 ≤ N ≤ 9$

* Pentru 50% din teste $1 ≤ N ≤ 10$

h2. Exemplu
table(example). |_. episoade.in |_. episoade.out |

| ((3,(4#5),(1#(2,6))))
3
1 2 3 4 5 6
3 5 4 1 2 6
3 5 1 4 2 6

| ((3, 2), 1) # (4, 5) # (7, 6, 8)
4
1 1 1 1 1 1 1 1
4 5 3 2 1 7 6 8
4 3 5 2 1 7 6 8
5 4 3 2 1 7 6 8

| 0
1
0

|

0
|

== include(page="template/taskfooter" task_id="episoade") ==