transformare

Pământul poate fi văzut ca o matrice cu $N$ linii și $M$ coloane, formate doar din cifrele $1$ și $0$, unde $1$ reprezintă o insulă și $0$ reprezintă apă. După mai multe cercetări, s-a descoperit că fiecare insulă are nevoie de cel puțin $K$ poziții vecine cu apă pentru a se transforma și a deveni apă. Vecinii unei insule pot fi pe direcțiile N, S, E sau V. De asemenea, insulele au proprietatea de a avea o singură direcție specială (NE, SE, SV sau NV) care reprezintă un alt vecin pentru insula respectivă. Transformarea unei insule în apă durează un an.

Cerință

Știind insulele, numărul $K$ pentru fiecare insulă, precum și fiecare direcție specială:

1. Să se determine câte insule se transformă în apă după un an.
2. Pentru $Q$ întrebări de forma $(x, y)$, să se determine după câți ani insula aflată pe poziția $(x, y)$ va deveni apă. Dacă pentru $(x, y)$ nu este posibil, se va afișa -1.

Date de intrare

Pe prima linie din consolă se citesc 4 numere naturale, $C$, $N$, $M$, $P$, în această ordine, separate printr-un spațiu. Pe următoarele $P$ linii se citesc câte patru numere naturale $x$, $y$, $K$, $d$, separate printr-un spațiu, reprezentând coordonatele unei insule, numărul de vecini necesari pentru a se transforma și direcția specială a sa. Pentru $d = 1$, direcția este NE, pentru $d = 2$, SE, pentru $d = 3$, SV, pentru $d = 4$, NV. Dacă $C = 2$, atunci pe următoarea linie se citește numărul de întrebări $Q$, iar pe următoarele $Q$ linii se citesc numerele $x$ și $y$, separate printr-un spațiu.

Date de ieșire

Dacă $C = 1$, atunci în consolă se va afișa numărul de insule care se transformă în apă după un an. Dacă $C = 2$, atunci se va afișa răspunsul la fiecare din cele $Q$ întrebări, pe câte o linie.

Restricții și precizări

• $1 \leq N, M \leq 1.000$
• $0 \leq K \leq 5$
• $1 \leq P \leq N \cdot M$
• $1 \leq Q \leq N \cdot M$
• $d \in \{1, 2, 3, 4\}$
• Există șansa ca unii vecini să se afle în afara Pământului. Aceștia nu vor fi luați în considerare. De exemplu, o insulă pe poziția $(1, 2)$ care are $K = 5$ este imposibil să devină apă deoarece vecinul din nord nu există.
• Se garantează că pentru fiecare întrebare din cele $Q$, $(x, y)$ reprezintă o poziție unde se află insulă.
• Coordonata $x$ reprezintă linia $x$ din matrice, iar coordonata $y$ reprezintă coloana $y$ din matrice.
• În coordonatele în care nu se află o insulă, se regasește apă.
• Pentru rezolvarea acestei probleme în limbajul C++, cercetătorii recomandă folosirea următoarelor linii de cod la începutul funcției main():

ios::sync_with_stdio(0);
cin.tie(0);

Exemplul 1

stdin

1 4 5 9
1 1 1 2
1 2 2 3
1 5 2 1
2 2 4 3
3 4 2 1
4 2 3 1
4 3 2 2
4 4 4 4
4 5 0 1

stdout

7

Exemplul 2

stdin

2 4 5 9
1 1 1 2
1 2 2 3
1 5 2 1
2 2 4 3
3 4 2 1
4 2 3 1
4 3 2 2
4 4 4 4
4 5 0 1
5
1 1
1 5
2 2
4 3
4 4

stdout

1
1
1
2
3

Explicație

Imaginea de mai jos corespunde ambelor exemple. Numerele de pe o insulă reprezintă valoarea $K$ a insulei, săgețile reprezintă direcția specială a insulei, iar dacă valoarea $K$ a insulei este de culoare roșie, înseamnă că acea insulă reprezintă o întrebare din cele $Q$.

Să discutăm despre insula de pe poziția $(3, 4)$. Aceasta are $K = 2$, deci trebuie să aibă cel puțin 2 vecini care trebuie să fie apă pentru a se putea transforma și ea în apă. Direcția specială a acestei insule este în NE (nord-est). Astfel, vecinii apă a acestei insule sunt în N, NE, E și V. Cum $4 \geq K = 2$, această insulă se va transforma în apă.

Insulele care se transformă în apă după primul an sunt: $\{(1,1), (1,2), (1,5), (2,2), (3,4), (4,2), (4,5)\}$.