bonsai

În grădina palatului de vară, maestrul grădinar Andrei caută locul perfect pentru amplasarea unui bonsai prezidențial. Grădina palatului este formată din mai multe parcele, dispuse pe $N$ linii și $M$ coloane. Deoarece grădina palatului este frecventată de turiști, fiecărei parcele îi este asociat un număr natural, reprezentând importanța parcelei respective.

Bonsaiul prezidențial poate fi plantat doar sub forma unei cruci simetrice (un centru și $4$ brațe egale pe direcțiile Nord, Sud, Est, Vest), care nu conține valori nule (parcele cu importanța $0$) și are număr maxim de parcele pe care se poate amplasa un bonsai. Un bonsai este definit de centrul său $(i, j)$ și de raza maximă posibilă $R$, cu care se poate extinde pe toate cele $4$ direcții (numărul de parcele al unui braț, fără a număra centrul). Un bonsai cu $R = 0$ ocupă o singură parcelă (centrul), iar un bonsai cu $R = 1$ ocupă centrul și cei $4$ vecini: $(i - 1, j)$, $(i + 1, j)$, $(i, j - 1)$, $(i, j + 1)$.

Andrei are trei criterii diferite de alegere, în funcție de cerința președintelui:

• Criteriul simplitate: Președintele își dorește un bonsai simplu de rază $R = 0$, astfel Andrei trebuie să caute toate locurile posibile în care se poate amplasa un bonsai de rază $R = 0$.
• Criteriul măreție: Președintele își dorește cel mai extins bonsai posibil, astfel Andrei este nevoit să caute raza maximă $R_{max}$ pe care o poate avea un bonsai în grădină.
• Criteriul vizibilitate: Președintele își dorește ca mai marea vizibilitate turistică pentru bonsaiul său, astfel Andrei este nevoit să caute locul în care, dacă ar planta bonsaiul, acesta ar avea importanță maximă. Importanța unui loc în care bonsaiul poate fi plantat este reprezentată de suma importanței parcelelor pe care le acoperă.

Cerință

Se dau $C$, reprezentând cerința care trebuie rezolvată ($C = 1$, $C = 2$ sau $C = 3$), $N$, $M$, dimensiunile grădinii și $N \times M$ valori naturale, reprezentând importanța fiecărei parcele.

• Dacă $C = 1$, ajutați-l pe Andrei să determine în câte locuri posibile din grădină ar putea planta un bonsai de rază $R = 0$;
• Dacă $C = 2$, ajutați-l pe Andrei să determine raza maximă $R_{max}$ a unui bonsai care poate fi plantat în grădină;
• Dacă $C = 3$, ajutați-l pe Andrei să determine locul cu importanța maximă în care poate planta bonsaiul, precum și coordonatele $(i, j)$ ale centrului acestuia. Dacă există mai multe locuri cu aceeași importanță maximă, se va alege cel cu raza $R$ cea mai mare. Dacă există mai multe astfel de locuri cu importanță egală și cu aceeași rază $R$, se va alege locul cu $i$ minim, iar în caz de egalitate, cel cu $j$ minim.

Date de intrare

Pe prima linie a fișierului bonsai.in se află un număr natural $C$, care reprezintă cerința ($1$, $2$ sau $3$). Pe a doua linie se află două numere naturale $N$ și $M$, cu semnificația din enunț. Următoarele $N$ linii conțin câte $M$ valori, reprezentând importanța fiecărei parcele. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire bonsai.out se află:

• Un singur număr: $P$, care reprezintă numărul de locuri din grădină în care Andrei poate planta un bonsai de rază $R = 0$, dacă $C = 1$;
• Un singur număr: $R_{max}$, reprezentând raza maximă a unui bonsai care poate fi plantat în grădină, dacă $C = 2$;
• Trei numere separate prin câte un spațiu: $S$, $i$, $j$, care reprezintă suma parcelelor ocupate de bonsaiul de importanță maximă și linia, respectiv coloana pe care se află centrul bonsaiului determinat, dacă $C = 3$.

Restricții și precizări

• $1 \le N, M \le 1000$;
• Importanța fiecărei parcele este un număr natural $\le 1000$;
• Valoarea $0$ reprezintă un obstacol și nu poate face parte din locul bonsaiului;
• Se garantează că există cel puțin o parcelă cu importanță nenulă;
• Un bonsai nu se poate extinde în afara grădinii.

Exemplul 1

bonsai.in

1
3 6
0 1 0 0 1 1
1 1 1 1 1 1
0 1 0 0 1 0

bonsai.out

9

Explicație

Parcelele situate în pozițiile $(1,2)$, $(1,5)$, $(1,6)$, $(2,1)$, $(2,3)$, $(2,4)$, $(2,6)$, $(3,2)$ și $(3,5)$ pot fi centre pentru un bonsai prezidențial de rază $R = 0$. Parcelele $(2,2)$ și $(2,5)$ pot fi centre pentru un bonsai de rază $R = 1$, dar nu sunt considerate valide.

Exemplul 2

bonsai.in

2
3 6
0 1 0 0 1 0
1 1 1 1 1 1
0 1 0 0 1 0

bonsai.out

1

Explicație

Există două locuri posibile pentru plantarea unui bonsai prezidențial cu raza maximă $R = 1$:

• Primul cu centrul în $(2,2)$: vecinii sunt $(1,2)$, $(3,2)$, $(2,1)$, $(2,3)$. Toți având valoarea $1$;
• Al doilea cu centrul în $(2,5)$: vecinii sunt $(1,5)$, $(3,5)$, $(2,4)$, $(2,6)$. Toți având valoarea $1$.

Astfel, $R_{max} = 1$ și sunt 2 parcele care fi în centru.

Exemplul 3

bonsai.in

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

bonsai.out

13 2 2

Explicație

Avem mai multe locuri posibile pentru amplasarea bonsaiului prezidențial, cele mai relevante fiind:

1. Bonsaiul prezidențial cu centrul în $(2,2)$ are raza $R = 1$ și importanța lui este $5$ (centru) $+ 2$ (nord) $+ 2$ (sud) $+ 2$ (vest) $+ 2$ (est) $= 13$.
2. Bonsaiul cu centrul în $(4,4)$ are raza $R = 0$ (valorile vecinilor în cele patru puncte cardinale sunt $0$ sau în afara tabloului bidimensional). Importanța este $9$.

Maximul importanței este $13$ și se obține pentru bonsaiul prezidențial cu centrul în $(2,2)$.

Exemplul 4

bonsai.in

3
3 6
0 2 0 0 0 0
2 2 2 0 10 0
0 2 0 0 0 0

bonsai.out

10 2 2

Explicație

Avem două posibilități:

1. Bonsaiul prezidențial cu centrul în $(2,2)$ are $R = 1$ și importanța $2 + 2 + 2 + 2 + 2 = 10$.
2. Bonsaiul prezidențial cu centrul în $(2,5)$ are $R = 0$ și importanța $10$.

Se alege bonsaiul prezidențial cu raza $R$ cea mai mare, adică bonsaiul cu centrul în $(2,2)$.