splatoon

Se consideră un tablou bidimensional format din $N$ linii și $N$ coloane, care conține celule libere codificate cu valoarea $0$ și celule blocate, codificate cu valoarea $1$. $M$ jucători sunt poziționați în celule diferite ale matricei. Un jucător poate fi poziționat într-o celulă liberă sau într-o celulă blocată. Începând cu momentul $t_0 = 0$, la fiecare moment întreg de timp $t$, fiecare jucător colorează celulele libere aflate la distanța $t$ de poziția în care se află.

Definim distanța dintre două celule $(i_1, j_1)$ și $(i_2, j_2)$ ca fiind egală cu $max(|i_1 - i_2|, |j_1 - j_2|)$, unde $i_1$ și $i_2$ corespund indicilor liniilor pe care se află cele două celule, iar $j_1$ și $j_2$ corespund coloanelor.

Cerința

Scrieți un program care citește un număr natural $N$, valorile matricei și pozițiile inițiale ale jucătorilor și afișează la ieșire răspunsul la $Q$ întrebări de forma: “Care este primul moment de timp după care avem cel puțin $P$ celule colorate în matrice?”. În cazul în care pentru o întrebare nu se vor putea colora $P$ celule libere (după oricât de mult timp), se va afișa ca răspuns pentru acea întrebare valoarea $-1$.

Date de intrare

Prima linie conține numărul $N$, iar fiecare din următoarele $N$ linii, câte $N$ numere separate prin câte un spațiu, corespunzând tipului celulelor de pe linia corespunzătoare din matrice.

Linia $N + 2$ conține numărul de jucători $M$, iar fiecare din următoarele $M$ linii câte două numere naturale, separate prin spațiu, reprezentând numărul liniei, respectiv, numărul coloanei în care se află fiecare din cei $M$ jucători.

Linia $M + N + 3$ conține numărul natural $Q$, reprezentând numărul de întrebări, iar ultima linie conține $Q$ numere naturale separate prin câte un spațiu, reprezentând valorile lui $P$, pentru fiecare dintre cele $Q$ interogări.

Întrucât volumul datelor de intrare este foarte mare, vă recomandăm, în cazul în care folosiți pentru citire biblioteca iostream din standardul C++, să adăaugați la începutul funcției main următoarele instrucțiuni:

std::ios_base::sync_with_stdio(false);
std::cin.tie(0);

Date de ieșire

Ieșirea constă într-o singură linie, care va conține $Q$ numere, separate prin câte un spațiu, corespunzătoare răspunsurilor la întrebările date, în ordinea în care au fost citite.

Restricții și precizări

• $3 \leq N \leq 1500$
• $1 \leq M, Q \leq N^2$
• $1 \leq P \leq 10^9$
• Liniile și coloanele sunt indexate începând cu $1$.

Exemplu

stdin

8
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
2
3 3
6 6
3
35 16 1000

stdout

2 1 -1

Explicație

După momentul de timp $t = 0$, se va colora doar celula $(3, 3)$. (Total: $1$)

După momentul de timp $t = 1$, se vor mai colora în plus celulele $(2, 2)$, $(2, 3)$, $(2, 4)$, $(3, 2)$, $(3, 4)$, $(4, 2)$, $(4, 3)$, $(4, 4)$, $(5, 6)$, $(5, 7)$, $(6, 5)$, $(6, 7)$, $(7, 5)$, $(7, 6)$, $(7, 7)$. (Total: $16$)

După momentul de timp $t = 2$, vom avea în total colorate $40$ de celule.

Pentru prima interogare, primul moment de timp după care avem cel puțin $35$ de celule colorate este $2$.

Analog, pentru a doua interogare, răspunsul este $1$.

Nu se vor putea colora niciodată $1000$ de celule, răspunsul fiind $-1$.