Ana si Ion
au o pasiune comuna pentru sah si joaca ori de câte 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 încearca sa reconstituie acum ultima configuratie.
Ion îsi 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 îsi
aminteste exact pozitiile în care a mutat, dar îsi aminteste directiile
în care s-a deplasat tura.
Cerinta
Scrieti un program care
sa determine pozitiile în 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, reprezentând 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,
reprezentând 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).
Date de
iesire
Fisierul de iesire sah.out
va contine pe prima linie un numar natural p,
reprezentând numarul de pozitii finale posibile.
Pe urmatoarele p linii sunt scrise
pozitiile finale posibile, câte 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 în
ordinea coloanelor.
Restrictii si precizari
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.