Nosaukums
Spiegi (spiegi)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
88%

Definīcija

Luka ir ieradies uz Nacionālajām informātikas sacensībām dažās dienas agrāk, cerībā noklausīties kādas no uzdevumu sastādītāju sarunām. Viņš zin, ka uzdevumu sastādītāji mēdz pastaigāties pa pilsētu, paklusām apspriežot uzdevumu idejas. Tāpēc Luka ir nolēmis izmantot savus draugus un paziņas, lai izveidotu kārtīgu spiegu tīklu, kas noklausītos uzdevumu sastādītāju sarunas.

Pilsēta ir būvēta tā, ka to var aprakstīt ar plaknes punktu palīdzību. Uzdevumu sastādītāji sāk savu pastaigu punktā (0,0) un visa pastaiga sastāv no vienības garuma nogriežņiem. Katru nogriezni var veikt četros virzienos: uz Austrumiem (x koordināta tiks palielināta par 1), uz Rietumiem (x koordināta tiks samazināta par 1), uz Ziemeļiem (y koordināta tiks palielināta par 1) vai uz Dienvidiem (y koordināta tiks samazināta par 1). Katru nogriezni uzdevumu sastādītāji veic tieši vienā minūtē.

Lukas spiegi atrodas noteiktos(dažādos) fiksētos punktos ar koordinātām un var noklausīties uzdevumu sastādītāju sarunu tikai tajos brīžos, kad uzdevumu sastādītāji atrodas tajā pašā punktā kur tie atrodas, vai arī tajos punktos, kuru koordinātas ir veseli skaitļi un kuru x un y koordinātas atšķiras no attiecīgā spiega atrašanās punkta koordinātas ne vairāk kā par 1.

Luka savus spiegus ir sanumurējis ar naturāliem skaitļiem pēc kārtas, sākot no 1.

Uzrakstiet programmu, kas nosaka, kuri no Lukas spiegiem varēja noklausīties uzdevumu sastādītāju sarunas!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dota naturāla skaitļa N(spiegu skaits, 1 ≤N≤1000) vērtība.

Katrā no nākošajām N faila rindām dotas divu veselu skaitļu X un Y vērtības - viena Lukas spiega atrašanās punkta koordinātas, -10000≤X,Y≤10000. Starp skaitļiem ir tukšumsimbols. i-tā spiega koordinātas dota faila i+1-ajā rindā (1≤i≤N).

Faila nākošajā rindā dota naturāla skaitļa K (1≤K≤100000) vērtība - uzdevuma sastādītāju veikto nogriežņu skaits.

Faila nākošajā rindā ir K simboli, kas norāda katra uzdevumu sastādītāju veiktā nogriežņa virzienu. Katrs simbols var būt I(ja nogrieznis veikts uz Austrumiem), S(uz Ziemeļiem), Z(uz Rietumiem), J(uz Dienvidiem).


Izvaddatu raksturojums

Izvaddatos jāizvada to spiegu numuri, kuriem izdevās noklausīties uzdevumu sastādītāju sarunu. Spiegu numuri jāizvada augošā secībā pa vienam katrā rindā.

Ja nevienam spiegam nav izdevies noklausīties uzdevuma sastādītāju sarunu, faila vienīgajā rindā jāizvada skaitlis -1.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
5
1 2
1 3
1 4
1 5
0 5
5
SSZSS
Stdout
1
2
5

Stdin
3
2 0
-1 3
-2 -1
10
SISSZZZJII
Stdout
1
2

Stdin
4
-1 -3
3 -1
-3 3
3 3
11
SZJJIISSSZZ
Stdout
-1

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.