episoade

Episoade

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

Poveste şi cerinţă...

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:
 
* î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 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
| 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>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
|
 
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$ ...

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$ ...

Î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 ≤ 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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

| 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
|

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

3626