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 dintre 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 kp reprezentând răspunsul la cea de-a p-a întrebare.

Restricţii

• 4 ≤ L, C ≤ 1000
• 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ă

Exemple

acces.in	acces.out	Explicaţii
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	5 14 11 3	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)

autor: Prof. Dan Pracsiu

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com