Vasile ar vrea sa câstige un premiu la Olimpiada Nationala,
dar nu este prea grozav pregatit. Din intâmplare, el a auzit ca autorii
problemelor au sosit cu 10 zile mai devreme in Utopia, orasul in care va avea
loc Olimpiada, si ca ei fac plimbari zilnice prin oras, timp in care discuta
despre probleme.
Asa ca Vasile s-a decis sa-si puna in functiune reteaua de
spionaj (formata din rude si prieteni).
Utopia este un oras astfel construit incât arata ca o retea rectangulara. Autorii problemelor pleaca la plimbare din punctul de coordonate (0,0), deplasându-se de-a lungul strazilor. Ei pot isi pot schimba directia in puncte de coordonate intregi, in una dintre cele 4 directii: Est (caz in care abscisa lor x va creste cu 1), Nord (caz in care ordonata lor y va creste cu 1), Vest (abscisa lor x scadea cu 1) sau SUD (ordonata lor y scadea cu 1).
Spionii lui Vasile sunt pozitionati in diferite puncte de coordonate intregi si pot auzi frânturi de conversatie daca si numai daca ei se afla in aceeasi pozitie cu autorii problemelor sau in una dintre cele 8 pozitii adiacente.
Cerinta
Scrieti un program care sa determine care spioni au auzit frânturi de conversatie.
Date de intrare
Prima linie a fisierului de intrare spioni.in contine un numar natural N, reprezentând numarul de spioni. Spionii sunt numerotati distinct de la 1 la N. Urmatoarele N linii contin câte doua numere intregi X Y separate prin spatiu, reprezentând, in ordine, abscisele si respectiv ordonatele pozitiilor celor N spioni.
Pe urmatoarea linie se afla un numar natural K. Urmatoarea linie contine K caractere care ne indica traseul plimbarii. Aceste caractere pot fi N (pentru nord), S (pentru sud), E (pentru est) si V (pentru vest).
Date de iesire
Fisierul de iesire spioni.out contine numerele de ordine ale spionilor care au auzit discutiile autorilor problemei, in ordine strict crescatoare, fiecare numar pe o linie separata. Daca nici unul dintre spioni nu a auzit conversatia, atunci fisierul de iesire va contine o singura linie pe care se afla valoarea –1.
Restrictii
1<=N<=1000
-10000 <=X, Y <=10000
1 <= K <= 100000
Exemple
spioni.in
spioni.out
spioni.in
spioni.out
spioni.in
spioni.out
4
-1 -3
3 -1
-3 3
3 3
11
NVSSEENNNVV
-1
3
2 0
-1 3
-2 -1
10
NENNVVVSEE
1
2
5
1 2
1 3
1 4
1 5
0 5
5
NNVNN
1
2
5
prof. Emanuela
Cerchez
Liceul de
Informatica "Grigore Moisil" Iasi