Rezervatie naturala

Pentru protejarea faunei şi florei sălbatice, în munţii Rodnei, s-a constituit rezervaţia naturală Piatra Rea. Rezervaţia se reprezintă pe hartă ca un tablou cu $L$ linii şi $C$ coloane. Tabloul este constituit din $L \times C$ celule pătrate de latură $1$. Printre plantele protejate de lege, sunt şi $N$ copaci care au fost declaraţi monumente ale naturii, numerotaţi de la $1$ la $N$. Fiecare copac este poziţionat în centrul unei celule. Nu există doi copaci care ocupă aceeaşi poziţie. În vederea limitării accesului în rezervaţie, s-a propus construirea unei împrejmuiri, formată din segmente identice, cu lungimea egală cu cea a laturii unei celule. Segmentele sunt plasate pe conturul celulelor. Construcţia împrejmuirii începe din colţul stânga-sus al primei celule a tabloului, situată pe linia $1$ şi coloana $1$, şi se termină în acelaşi punct. Nu există alte puncte de intersecţie.

Cerinţă

Cunoscând poziţiile tuturor segmentelor împrejmuirii, dimensiunea rezervaţiei şi poziţiile celor $N$ copaci monumente ale naturii, să se identifice copacii care se găsesc în interiorul suprafeţei împrejmuite.

Date de intrare

Fişierul de intrare rezerv.in conţine pe prima linie numerele naturale $L$ şi $C$. Pe linia a doua un şir de direcţii format doar din caracterele N, S, E, V, reprezentând dispunerea segmentelor (respectiv Nord, Sud, Est, Vest). Primul caracter din şir, reprezintă direcţia pe care se construieşte primul segment şi poate fi doar E sau S. Al $i$-lea caracter din şir, cu $i$ cuprins între $2$ şi numărul de segmente, reprezintă direcţia pe care se construieşte segmentul $i$, pornind din capătul liber al segmentului $i - 1$. Pe linia a treia, se găseşte numărul natural $N$. Pe fiecare dintre următoarele $N$ linii sunt câte două numere naturale, reprezentând linia şi coloana corespunzătoare copacilor $1, 2, 3, \dots, N$.

Date de ieşire

În fişierul de ieşire rezerv.out se va scrie pe prima linie un număr natural $K$, reprezentând numărul de copaci care se găsesc în interiorul împrejmuirii. Pe linia a doua, despărţite prin câte un spaţiu, se vor scrie $K$ numere naturale în ordine crescătoare, reprezentând numerele de ordine ale copacilor aflaţi în interiorul suprafeţei împrejmuite. În situaţia în care niciun copac nu se găseşte în interiorul suprafeţei împrejmuite, în fişierul de ieşire se va afişa o singură valoare: $0$.

Restricţii şi precizări

• $1 \leq L, C \leq 200$
• $1 \leq N \leq 1 \ 000$
• $4 \leq \text{numărul de segmente ale împrejmuirii} \leq 10 \ 000$

Exemplul 1

rezerv.in

5 4
ESSENNEESVSSVVVNNN
3
3 1
1 4
1 2

rezerv.out

2
1 2

Exemplul 2

rezerv.in

4 5
SSSESENEEENNVSVVVNEENVVV
4
4 2
3 4
2 3
1 1

rezerv.out

3
1 2 4

Explicaţie

Datele de test de mai jos corespund figurilor $1$ şi $2$.