Koľko skokov spraví vrabec za sto rokov?
Táto filozofická otázka nedáva Prefixovi v noci spávať. Posledných $s$ storočí si teda pre každého z $r$ vrabcov pozorne zapisoval koľko skokov spravil. Keďže sa však počet skokov za storočie výrazne líši od vrabca k vrabcovi, a dokonca aj pre každého vrabca počas rôznych storočí, tieto získané informácie ho neuspokojili.
Aby túto problematiku mohol analyzovať hlbšie, usporiadal si vrabcov v jeho zápisníku podľa nadmorskej výšky jeho hniezda. To mu nepomohlo, ale nič ďalšie ho nenapadlo. Rozhodol sa teda že zozbiera svoje materiály a publikuje ich v slávnom vedeckom časopise -- možno tak zaujme niekoho múdrejšieho, ktorý túto otázku predsa len zodpovie. Aby to však nevyzeralo že je úplne neschopný, chcel by ešte k svojej práci pripojiť veľký kus dát, ktoré síce veľký zmysel nemajú, ale možno na neskúseného riešiteľa spravia dojem.
Dostanete Prefixove záznamy -- pre každého z $r$ vrabcov jeden riadok s $s$ číslami, udávajúcimi počet skokov v danom storočí.
Prefix sa rozhodol že sa bude tváriť akoby študoval koreláciu medzi počtom skokov a výškou vrabcovho hniezda v rôznych časových intervaloch. Bude si teda hádzať veľkou kockou aby dostal štyri čísla $a,b,c,d$, a pripíše do svojej práce počet skokov, ktorý spravili vrabci s $a$-tym až $c$-tym najvyšším hniezdom počas $b$-teho až $d$-teho storočia.
V prvom riadku vstupu sú dve čísla $1 \leq r,s \leq 1\,000$. Nasleduje $r$ riadkov, v každom z nich $s$ nezáporných celých čísel nepresahujúcich $10^9$ - pre každého vrabca, začínajúc tým s najvyšším hniezdom, počet jeho skokov počas prvého, druhého, ... , $s$-teho storočia. Potom nasleduje číslo $1 \leq q \leq 10^6$, počet Prefixovych otázok. Nasleduje $q$ riadkov, v každom z nich je jedna Prefixova otázka $a\,b\,c\,d$, $1 \leq a \leq c \leq r$, $1 \leq b \leq d \leq c$.
Počet skokov ktorý spravil vrabec $x$ v $y$-tom storočí si označíme $v_{xy}$. Na otázku $a\,b\,c\,d$ odpovedzte súčtom čísel $v_{xy}$, kde $a \leq x \leq c$ a $b \leq y \leq d$.
4 4
1 2 3 4
3 3 3 3
5 1 2 0
7 2 7 1
3
1 1 4 4
3 2 3 2
2 2 3 4
47
1
12
2 3
1 2 3
4 5 6
2
1 1 2 3
1 2 2 3
21
16