Fişierul intrare/ieşire:	sah2.in, sah2.out	Sursă	Campion 2006-2007
Autor	Emanuela Cerchez	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.05 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sah2

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.

Cerinta

Scrieti un program care sa determine pozitiile in care s-ar putea afla la final tura mutata de Ana.

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₁ C₁ cu semnificatia piesa i este deplasata pe linia L₁, coloana C₁.
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).

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.

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

Exemplu

Cum se trimit solutii?