== 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 începutul jocului configuratia tablei de sah, precum si mutarile pe care el le-a facut. Ana îsi 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 în 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, reprezentând 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 câte un spatiu i L1 C1 cu semnificatia piesa i este deplasata pe linia L1, coloana C1.
Pe ultima linie din fisier este scrisa o secventa de Nr caractere din multimea {'N', 'S', 'E', 'V'} care reprezinta în directiile în 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 în ordinea liniilor; daca exista mai multe pozitii finale pe aceeasi linie, acestea vor fi scrise in ordinea coloanelor.

h2. Restrictii

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

* 1 < X<=50
* 1 < N <= 1000
* 0 < Nr <= 1000
* Piesele sunt numerotate de la 1 la N.
* Liniile tablei de sah sunt numeroate de sus în jos de la 1 la X, iar coloanele sunt numerotate de la stânga 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