Fall FLASG | Fortnite

One, two, three, scapa-ma de datorii! Two, three, four si cu tine ma insor! (ASG a spus asta odata catre cautarea binara)

După ce s-a jucat foarte mult Fortnite, ASG a visat mai multe insule din toate sezoanele. Fiind cuprins de nostalgie, își dorește să le viseze și în următoarele nopți, însă este restricționat doar la o anumită perioadă din vis.
Știm că visul poate fi reprezentat ca o matrice de $N$ linii și $M$ coloane, unde se află $K$ insule pe care ASG le-a visat. În următoarele $Q$ nopți, acesta se decide să viseze o submatrice din matricea visului. O insulă este constituită din una sau mai multe pătrățele din matrice, care sunt vecine pe cele $4$ direcții: Nord, Sud, Vest și Est. Putem avea insule care se suprapun.

ASG va cere ajutorul pentru a afla câte insule va visa în noaptea $i$.

Date de intrare

Pe prima linie se găsesc patru numere întregi, $N$, $M$, $K$ și $Q$.
Pentru fiecare dintre cele $K$ insule, datele se vor găsi pe două linii consecutive. Pe prima linie a fiecărei insule se află coordonata de start pe care ASG o cunoaște, urmată de $X$ direcții pe care ASG trebuie să le urmeze pentru a descoperi toată insula.
Pe a doua linie se află un șir de lungime $X$ ce conține direcțiile de deplasare, formate din literele:

• $N$ pentru Nord
• $S$ pentru Sud
• $V$ pentru Vest
• $E$ pentru Est

După ce sunt descrise toate insulele, urmează $Q$ linii, fiecare conținând câte patru numere întregi ce reprezintă coordonatele unei submatrice pe care ASG dorește să o viseze în noaptea respectivă. Primele două numere reprezintă colțul din stânga-sus al submatricei, iar ultimele două numere reprezintă colțul din dreapta-jos al acesteia.

Sarcina ta este să afli câte insule complete vor fi visate în fiecare dintre cele $Q$ nopți, având în vedere că o insulă este formată din celule adiacente în cele $4$ direcții (Nord, Sud, Vest, Est) și poate fi completă doar dacă este inclusă integral în submatricea selectată în noaptea respectivă.

Date de ieșire

La final, se vor afișa $Q$ linii, fiecare linie reprezentând numărul de insule complete visate în fiecare noapte.

Restricții și precizări

• $N \cdot M \leq 500 \ 000$
• $Q \leq 2 \cdot 10 ^ 5$
• $K \leq 100$
• O insulă este considerată visată doar dacă se află în totalitate în submatricea selectată pentru visul din noaptea respectivă. Dacă insula nu este complet inclusă în submatrice, ASG o va uita când se trezește.

Exemplul 1

stdin

4 4 1 2
2 2 4
SENE
2 2 3 4
2 2 3 3

stdout

1
0