Acces

Considerăm o matrice cu $L$ linii (numerotate de sus în jos de la $1$ la $L$) şi $C$ coloane (numerotate de la stânga la dreapta de la $1$ la $C$) care memorează doar valori $0$ şi $1$. Mai mult, valorile egale cu $1$ sunt grupate în mai multe dreptunghiuri pline, care nu se învecinează nici pe linii, nici pe coloane, nici pe diagonale. În exemplul din fig. 1 matricea este corectă deoarece cele $4$ dreptunghiuri de $1$ nu se învecinează. În schimb în fig. 2 există $2$ dreptunghiuri de $1$ învecinate pe coloană şi două învecinate pe diagonală, deci matricea este incorectă.

În această matrice se pot face deplasări doar pe direcţiile Vest şi Nord în elemente egale cu $0$, deci din poziţia $(i,j)$ se poate ajunge doar într-una din poziţiile $(i,j-1)$ şi $(i-1,j)$, marcate cu $0$. În acest fel, pornind de la o anumită poziţie, prin deplasări succesive, pot fi accesate un anumit număr de elemente ale matricei egale cu $0$. De exemplu, în fig. 1, din poziţia $(2,4)$ pot fi accesate $5$ componente egale cu $0$, iar din poziţia $(5,4)$ pot fi accesate $14$ componente egale cu $0$.

Trebuie să răspundeţi la $Q$ întrebări, fiecare întrebare fiind de forma: “Câte din elementele egale cu zero ale matricei pot fi accesate din poziţia $(i,j)$ ?”

Cerinţă

Scrieţi un program care să determine, pentru fiecare întrebare, câte elemente egale cu 0 din matrice pot fi accesate din poziţia precizată în cadrul întrebării.

Date de intrare

Pe prima linie a fişierului acces.in se află două numere naturale $L$ şi $C$ separate printr-un spaţiu, reprezentând numărul liniilor, respectiv numărul coloanelor matricei. Pe următoarele $L$ linii se găsesc câte $C$ cifre binare, separate prin câte un spaţiu, reprezentând elementele matricei. Pe linia următoare se află numărul natural $Q$, reprezentând numărul întrebărilor. Pe următoarele $Q$ linii se găsesc câte două numere naturale $i$ şi $j$, separate prin câte un spaţiu, reprezentând poziţia corespunzătoare unei întrebări.

Date de ieșire

Fişierul acces.out conţine $Q$ linii. Pe linia $p \ (1 ≤ p ≤ Q)$ se află un număr natural $k_p$ reprezentând răspunsul la cea de-a $p$-a întrebare.

Restricții și precizări

• $4 ≤ L, C ≤ 1 \ 000$
• $3 ≤ Q ≤ 500 \ 000$
• Pentru orice întrebare $i \ j$ se garantează că valoarea corespunzătoare din matrice este $0$.
• pentru toate testele, dreptunghiurile formate din valori de $1$ nu se învecinează

Exemplu

acces.in

5 7
0 0 0 0 1 1 1
0 1 1 0 1 1 1
0 1 1 0 0 0 0
0 1 1 0 1 0 0
0 0 0 0 1 0 1
4
2 4
5 4
4 7
3 1

acces.out

5
14
11
3

Explicație

Pentru prima întrebare, cele $5$ componente egale cu $0$ care pot fi accesate sunt cele din poziţiile $(1,1), (1, 2), (1,3), (1,4), (2,4)$.