Počet bodov:
Popis:  15b
Program:  15b

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu conditions_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Danovi na [email protected]

Farmár Fero nie je farmár. Ale chcel by byť. Na to však, samozrejme, potrebuje pole. Blízko jeho domu je veľký kus hospodárskej pôdy, ktorú nikto nevyužíva. Je ako stvorená pre neho. Keď ale Fero zistil tú strašnú cenu za každý meter štvorcový tejto pôdy, uvedomil si, že si môže dovoliť odkúpiť iba nejaký menší kúsok.

Celá hospodárska pôda má štvorcový tvar. Fero by z nej chcel nejaký obdĺžnik. Prečo zrovna obdĺžnik? Keby to bol nejaký krivoľaký útvar, ťažko by sa mu na ňom manévrovalo s kombajnom. A on na tom poli predsa nič iné robiť nebude.

Hospodárska pôda je naozaj rozsiahla. Je to štvorec rozmerov \(n \times n\) metrov. Niektoré jej časti sú úrodnejšie, ako iné. Terajší vlastník má pre každé políčko veľkosti \(1 \times 1\) meter spočítané, ako veľmi je úrodné. Na niektorých políčkach neprežije ani burina, na iných vie vyrásť aj kukurica. Nájdu sa dokonca aj tak neúrodné políčka, že im terajší vlastník priradil zápornú hodnotu. Všetky tieto dáta poskytol Ferovi. Vraj aby sa mohol dobre rozhodnúť.

Náš odhodlaný takmer-farmár začal hútať, ktorý obdĺžnik by si mal vybrať, aby bol čo najúrodnejší. Vytipoval si niekoľko kandidátov. Teraz ale pre každý z vytipovaných obdĺžnikov potrebuje vedieť, aká je jeho úrodnosť. Pomôžete mu vybrať jeho pole?

Úloha

Kus hospodárskej pôdy má rozmery \(n \times n\) metrov. Je tvorený políčkami rozmerov \(1 \times 1\) meter. Ide teda o akúsi mriežku s \(n\) riadkami a \(n\) stĺpcami. Pre každé políčko poznáte jeho úrodnosť vyjadrenú celým číslom. Fero sa vás opýta \(q\) otázok. Každá otázka predstavuje obdĺžnik na veľkom kuse hospodárskej pôdy. Pre každý takýto obdĺžnik je vašou úlohou spočítať súčet úrodností jeho políčok.

Formát vstupu

Na prvom riadku vstupu je číslo \(n\). To hovorí, že kus hospodárskej pôdy, z ktorej si Fero ide vyberať obdĺžnikové pole, má rozmery \(n \times n\) políčok. Platí, že \(1 \leq n \leq 2\,000\).

Nasleduje \(n\) riadkov. V každom z nich je \(n\) čísel. Číslo \(x_{ij}\) v \(i\)-tom riadku a \(j\)-tom stĺpci hovorí, že políčko v \(i\)-tom riadku a \(j\)-tom stĺpci hospodárskej pôdy má úrodnosť \(x_{ij}\). Platí, že \(-1\,000 \leq x_{ij} \leq 1\,000\).

Na ďalšom riadku je číslo \(q\) – počet otázok. Môžete predpokladať, že \(1 \leq q \leq 100\,000\).

Nasleduje \(q\) riadkov – jednotlivé otázky. Každý riadok obsahuje \(4\) čísla \(r_1\), \(c_1\), \(r_2\), \(c_2\). Odpoveďou na túto otázku je úrodnosť obdĺžniku, ktorý má ľavý horný roh v riadku \(r_1\) a stĺpci \(c_1\), a pravý dolný roh v riadku \(r_2\) a stĺpci \(c_2\). Platí, že \(0 \leq r_1, c_1, r_2, c_2 \leq n - 1\) a tiež, že \(r_1 \leq r_2\) a \(c_1 \leq c_2\).

Formát výstupu

Pre každú otázku vypíšte jej odpoveď na jeden riadok. Odpovede vypisujte v takom poradí, v akom ste dostali otázky. To znamená, že v prvom riadku bude odpoveď na prvú otázku, v druhom na druhú, atď.

Hodnotenie

Sú 3 sady vstupov. Platia pre ne nasledové horné obmedzenia pre hodnotu \(q\).

Číslo sady 1 2 3
\(q \leq\) \(10\) \(10\,000\) \(100\,000\)

Príklad

Input:

4
1 -2 -3 4
-2 4 -1 2
1 -2 3 5
0 -1 9 9
2
1 1 2 3
1 3 1 3

Output:

11
2
Prvý obdĺžnik, na ktorý sa Fero pýta, je na obrázku vyplnený zelenou farbou. Druhý je zarámovaný červernou čiarou.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.