Problema Livada 2

Andrei a primit în dar de la bunicul său o imensă livadă. Bunicul, fost profesor de matematică, a plantat în mod riguros pomi fructiferi, astfel pe N rânduri paralele, iar pe fiecare rând a plantat exact M pomi. În total, livada are N × M pomi. În figura de mai jos avem o livadă cu 3 rânduri (N = 3), iar pe fiecare rând câte 5 pomi (M = 5). Rândurile sunt numeroate de la 1 la N, iar coloanele de la 1 la M. Fiecare pom conține o cantitate de fructe cunoscută. Din nefericire, în zonă a apărut un stol de ciori lacome, care dau târcoale livezii, așteptând ca fructele să se coacă.

Andrei are la dispoziție o plasă dreptunghiulară de dimensiuni P × Q și dorește să acopere acea bucată din teren care conține cea mai mare cantitate de fructe.

Cerință

Livada fiind destul de mare, ajutați-l pe Andrei să găsească răspunsul la următoarele două întrebări:

1. Care sunt liniile din teren pe care se află un numar maxim de pomi uscați? Andrei consideră că un pom este uscat dacă numărul maxim de fructe pe care le poate culege este 2.
2. Care este parcela de teren pe care o acoperă cu plasa, pentru a culege un număr maxim de fructe? Se vor afișa: cantitatea de fructe culese, precum și coordonatele colțului din stânga-sus și dreapta-jos ale terenului acoperit. Dacă sunt mai multe parcele cu număr maxim de fructe, atunci se va afișa parcela care are colțul din stânga-sus cu linia de indice maxim, iar dacă sunt mai multe parcele situate pe aceeași linie, cea de coloană maximă.

Date de intrare

Programul citește din fișierul livada.in de pe prima linie numărul C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). A doua linie conține numerele N, M, P, Q cu semnificația de mai sus. Iar de pe următoarele N linii se citesc câte M numere naturale, reprezentând cantitatea de fructe din fiecare pom.

Date de ieșire

Fișierul livada.out va conține:

• Dacă C = 1 numerele de ordine ale liniilor separate printr-un spațiu.
• Dacă C = 2 atunci pe prima linie avem cantitatea maximă de fructe pe care poate sa o culeagă din parcela acoperită, iar pe următoarea linie, separate prin spațiu coordonatele colțului din stânga-sus, respectiv dreapta-jos.

Restricții și precizări

• 1 ≤ N, M, P, Q ≤ 1000
• Cantitatea de fructe din fiecare pom este un număr natural mai mic decât 10.000
• Plasa se poate roti cu 90 de grade, iar laturile plasei sunt paralele cu laturile terenului
• Dacă livada nu conține niciun pom uscat se va afișa NU EXISTA
• Pentru cerința 1 se acorda 30 de puncte

Exemple