Plantatie

plantatie

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

Zaharel si cu Nargy au cumparat recent o plantatie de tutun de marime $N x N$ metri. Dupa o analiza complexa, ei au calculat pentru fiecare bucata de $1 x 1$ metri productivitatea ei, adica cantitatea de tutun pe care o obtin intr-o zi plantand tutun pe acea bucata.
Pentru a mari productivitatea ei vor sa analizeze doar anumite bucati patratice din intreaga plantatie. Pentru asta ei si-au pus $M$ intrebari de forma: "Care este bucata $1 x 1$ de productivitate maxima dintr-un patrat cu coltul stanga-sus pe linia $i$ si coloana $j$ si latura $k$?". Scrieti un program sa-i ajute pe cei doi sa raspunda la aceste intrebari.

Poveste si cerinta...

h2. Date de intrare

Prima linie a fisierului $plantatie.in$ va contine numerele naturale $N$ si $M$ separate prin cate un spatiu. Urmatoarele $N$ linii vor contine cate $N$ numere naturale separate prin spatii, reprezentand productivitatea bucatilor $1 x 1$ din plantatie. Urmatoarele $M$ linii vor contii triplete de numere $i j k$, reprezentand intrebarile pe care le au cei doi.

...

h2. Date de iesire

Fisierul de iesire $plantatie.out$ contine $M$ linii, reprezentand raspunsurile la intrebari, in ordinea din fisierul de intrare.

...

h2. Restrictii

* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 75.000$
* Productivitatea unei bucati din plantatie este un numar natural din intervalul $[0, 1.000.000.000]$
* Liniile si coloanele plantatiei sunt numerotate cu numere de la $1$ la $N$
* Toate intrebarile vor reprezenta patrate aflate complet in interiorul plantatiei

... ≤ ...

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

| 8 3
7  8  0  0  0  0  5  5
0  0  0  0  0  0  5  5
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  1  2  3  4
0  0  0  0  5  6  7  8
0  0  0  0  9 10 11 12
1  1  1  1 14 15 16 17
1 1 8
4 5 3
2 2 6
| 17
7
11

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

|

h3. Explicatie
 
...
 

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

1562