== include(page="template/taskheader" task_id="inundatie") ==

Poveste şi cerinţă...

Mitruţ, motanul încălţat, vă dă harta unui oraş fermecat de furnici care are forma unei matrice dreptunghiu­lare cu $N$ linii şi $M$ coloane. Se poate considera că în fiecare căsuţă $(i, j)$ a matricei, cu $i=1,2,…,N$ şi $j=1,2,…,M$, se află un bloc al cărui număr de etaje $e{~i,j~}$ se cunoaşte. Fiindcă şi Mitruţ a gustat din prăjitura magică, a dobândit puteri supranaturale şi îşi pune acum problema pedepsirii furnicilor lacome prin inundarea oraşului. Astfel, Mitruţ îşi pune $Q$ întrebări precum care este numărul total de locuinţe afectate dacă pompează apă în oraş până la etajul $eq{~k~}$ $(k=1,2,…,Q)$?
 
h2. Cerinţă
 
Răspundeţi la cele $Q$ întrebări puse de Mitruţ.

h2. Date de intrare

Fişierul de intrare $inundatie.in$ ...

Pe prima linie a fişierului de intrare $inundatie.in$ se află numerele naturale $N$ şi $M$. Urmează $N$ linii cu câte $M$ numere naturale fiecare. Numărul $j$ de pe linia $i$ reprezintă câte etaje are blocul situat în căsuţa $(i, j)$ pe harta lui Mitruţ. Următoarea linie conţine numărul natural $Q$, iar ultimele $Q$ linii din fişier conţin fiecare câte un număr natural ce reprezintă întrebarea pusă de Mitruţ.

h2. Date de ieşire

În fişierul de ieşire $inundatie.out$ ...

Fişierul de ieşire $inundatie.out$ trebuie să conţină răspunsurile la cele $Q$ întrebări puse de Mitruţ.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 300$
* $1 ≤ Q ≤ 100 000$
* $0 ≤ e{~i,j~} ≤ 1 000 000 000$ $(i=1,2,…,N, j=1,2,…,M)$
* $0 ≤ eq{~k~} ≤ 1 000 000 000$ $(k=1,2,…,Q)$
* Pentru $30%$ din teste: $Q ≤ 1000$ şi $N, M ≤ 50$.
* Fiecare etaj al unui bloc adăposteşte o singură locuinţă.
* Numerotarea etajelor începe de la $1$.
* Dacă $e{~i,j~} = 0$ atunci în căsuţa $(i, j)$ nu există un bloc.
* Pentru o întrebare $eq{~k~}$ trebuie inundate în întregime toate locuinţele care se află la un etaj mai mic decât $eq{~k~}$, în timp ce acele locuinţe care se află la un etaj mai mare sau egal trebuie să rămână neatinse.

h2. Exemplu
table(example). |_. inundatie.in |_. inundatie.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
7 3 5
0 2 0
5 0 2
4
2
4
1
5
| 6
16
0
19

|
h3. Explicaţie

...

Pentru prima întrebare a lui Mitruţ vor fi inundate toate locuinţele situate la etaje mai joase decât etajul $2$. Sunt $6$ astfel de locuinţe (locuinţele de la etajul $1$ din blocurile situate în $(1,1)$, $(1,2)$, $(1,3)$, $(2,2)$, $(3,1)$, $(3,3)$).

== include(page="template/taskfooter" task_id="inundatie") ==