sah2

Sah2

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

Poveste si cerinta...

Ana si Ion au o pasiune comuna pentru sah si joaca ori de cate ori au timp liber. Fiind persoane non-conformiste, si-au comandat table de sah de diferite dimensiuni, si seturi de piese speciale. Daca nu au timp sa termine o partida, pastreaza pe tabla de sah piesele asa cum sunt si continua a doua zi.
De data aceasta, a aparut o problema - Ionel, fiul lor, a rasturnat din greseala tabla de sah - si ei incearca sa reconstituie acum ultima configuratie.
Ion isi aminteste cu precizie cu arata ieri la inceputul jocului configuratia tablei de sah, precum si mutarile pe care el le-a facut. Ana isi aminteste ca a jucat ciudat - tot jocul a mutat aceeasi piesa, o tura. Nu isi aminteste exact pozitiile in care a mutat, dar isi aminteste directiile in care s-a deplasat tura.
 
h2. Cerinta
 
Scrieti un program care sa determine pozitiile in care s-ar putea afla la final tura mutata de Ana.

h2. Date de intrare

...

Fisierul de intrare $sah.in$ contine pe prima linie doua numere naturale separate printr-un spatiu $X$ $N$, reprezentand dimensiunea tablei de sah, respectiv numarul de piese de pe tabla de sah.
Urmatoarele $N$ linii contin informatii despre pozitia pieselor de pe tabla. Mai exact, pe linia $i+1$ se afla pozitia piesei $i$ sub forma a doua numere naturale printr-un spatiu $L$ $C$, reprezentand linia si respectiv coloana pe care se afla piesa.
Ultima pozitie corespunde turei pe care o muta Ana.
Pe linia urmatoare se afla un numar natural $Nr$, reprezentand numarul de mutari efectuate de Ion si respectiv de Ana.
Pe fiecare dintre urmatoarele $Nr$ linii se afla informatii despre mutarile facute de Ion.
Mai exact, pe linia $N+2+j$ sunt scrise $3$ numere naturale separate prin cate un spatiu $i$ $L{~1~}$ $C{~1~}$ cu semnificatia piesa $i$ este deplasata pe linia $L{~1~}$, coloana $C{~1~}$.
Pe ultima linie din fisier este scrisa o secventa de $Nr$ caractere din multimea {'$N$', '$S$', '$E$', '$V$'} care reprezinta in directiile in care a mutat Ana tura (caracterul $i$ din aceasta secventa corespunde celei de a $i$-a mutari).
 

h2. Date de iesire

...

Fisierul de iesire $sah.out$ va contine pe prima linie un numar natural $p$, reprezentand numarul de pozitii finale posibile.
Pe urmatoarele $p$ linii sunt scrise pozitiile finale posibile, cate o pozitie pe o linie. O pozitie este descrisa prin doua numere naturale separate printr-un spatiu $L$ $C$, cu semnificatia "pe linia $L$ si coloana $C$ este o pozitie finala posibila". Pozitiile finale vor fi scrise in ordinea liniilor; daca exista mai multe pozitii finale pe aceeasi linie, acestea vor fi scrise in ordinea coloanelor.

h2. Restrictii

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

* $1$ < $X$ &le; $50$
* $1$ < $N$ &le; $1000$
* $0$ < $Nr$ &le; $1000$
* Piesele sunt numerotate de la $1$ la $N$.
* Liniile tablei de sah sunt numeroate de sus in jos de la $1$ la $X$, iar coloanele sunt numerotate de la stanga la  dreapta de la $1$ la $X$.
* Ana si Ion muta alternativ, Ion a fost primul la mutare.
* O tura poate fi mutata numai pe $4$ directii:
** nord (codificat $N$) - pe o linie cu indice mai mic, aceeasi coloana;
** sud (codificat $S$) - pe o linie cu indice mai mare si aceeasi coloana
** est (codificat $E$) - pe o coloana cu indice mai mare si aceeasi linie
** vest (codificat $V$) - pe o coloana cu indice mai mic si aceeasi linie
* La o mutare o piesa trebuie sa se deplaseze din pozitia curenta.

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 8
2 2
3 2
4 3
5 4
4 5
3 5
2 5
2 4
4
3 4 2
4 5 3
1 1 2
2 5 1
SVNV
| 4
2 1
2 2
3 1
3 2

|

h3. Explicatie
 
...
 

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