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

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:

Au venit Stelele şi e timpul ca Algorel să apară iar în viaţa mondenă. Ziarele au scris zilele trecute că Algorel în loc să se pregătescă pentru Stele se uită de zor la un serial de desene animate. Şi chiar aşa este... Tocmai a făcut rost de un nou sezon ce are $N$ episoade şi Algorel vrea să ştie în ce ordine ar putea să le vadă (fiindcă nu-i place ordinea originală). El are de la un prieten o expresie care descrie cum se leagă episoadele între ele. Expresia dată respectă 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

* într-o expresie pot apărea numerele de la $1$ la $N$ precum şi caracterele: {$()>#$}
* fiecare număr între $1$ şi $N$ apare o singură dată în expresie; fiecărui episod îi corespunde în mod unic un număr
* un grup de episoade este definit ca un singur episod sau o subexpresie ce decrie relaţii între mai multe episoade
* $>$ şi $#$ sunt operatori pe grupuri de episoade şi au următoarele proprietăţi:
** $ge{~1~} > ge{~2~}$ - grupul de episoade $ge{~2~}$ trebuie văzut imediat după grupul de episoade $ge{~1~}$
** $ge{~1~} # ge{~2~}$ # ... # ge{~k~} - grupurile de episoade pot fi văzute în orice ordine dar fără să se intercalaze
** $>$ are prioritate mai mare faţă de $#$
* parantezele pot apărea oriunde în expresie cu condiţia să fie bine închise

Pentru a va ajuta sa intelegeti regulile, Algorel va da si cateva exemple:

Pentru a vă ajuta să înţelegeţi regulile mai bine, Algorel vă pune la dispoziţie şi câteva exemple:

table(example). |_. expresie |_. ordini posibile |
| 1#2,3,4

table(example). |_. Expresie |_.  Ordini posibile |
| 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 1 2 6
  3 4 5 2 6 1
  3 5 4 1 2 6

  3 5 4 2 6 1

  3 5 4 2 6 1 |
| 1>2#3>4#5>6
| 1 2 3 4 5 6
  1 2 5 6 3 4
  3 4 1 2 5 6
  3 4 5 6 1 2
  5 6 1 2 3 4
  5 6 3 4 1 2

|

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.

Algorel are nişte ordini în care ar vrea să vadă episoadele. El vrea să ştie care din aceste ordini sunt posibile luând în considerare regulile descrise de expresie. Cum în ultimul timp s-a tot uitat la desene, nu prea ştie să rezolve problema şi a propus-o la concurs.

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 conţine pe prima linie expresia care descrie relaţiile dintre episoade. Pe a doua linie se află două numere: $T$ - numărul de ordini preferate de Algorel şi $N$ - numărul de episoade. Fiecare din următoarele $T$ linii descriu o anumită ordine: pe fiecare linie se află o permutare a numerelor de la $1$ la $N$; numerele sunt separate prin spaţii.

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$ veţi afişa $T$ linii: pe linia $i$ veţi scrie $1$ dacă ordinea $i$ din fişierul de intrare este posibilă conform regulilor expresiei sau $0$ în caz contrar.

h2. Restricţii

* $1 ≤ N ≤ 500$
* Lungimea expresiei nu depaseste 2000 de caractere
* $1 ≤ T ≤ 30$
* Pentru 50% din teste $1 ≤ N ≤ 9$

* $1 ≤ N ≤ 100$
* $1 ≤ T ≤ 20$
* Lungimea expresiei nu depăşeşte $1000$ caractere
* Expresia nu conţine spaţii
* Pentru $50%$ din teste nu vor aparea paranteze în expresie

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

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

| 1#2>3>4
  3 4
  1 2 3 4
  2 1 3 4
  2 3 4 1
| 1
0
1 |
| ((3>(4#5)>(1#(2>6))))
3 6

1 2 3 4 5 6
3 5 4 1 2 6
3 5 1 4 2 6
| 0
1

0 |
| 3#(2#1)
4 3
1 2 3
3 2 1
3 1 2
1 3 2
| 1
1
1

0
|

3626