| Fişierul intrare/ieşire: | plantatie.in, plantatie.out | Sursă | preONI 2007, Runda 2 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
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 × 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 × 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.
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 × 1 din plantatie. Urmatoarele M linii vor contii triplete de numere i j k, reprezentand intrebarile pe care le au cei doi.
Date de iesire
Fisierul de iesire plantatie.out contine M linii, reprezentand raspunsurile la intrebari, in ordinea din fisierul de intrare.
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
Exemplu
| 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 |
