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

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi