Lumtirogla++

Cerință

Tudor și Luca sunt doi tineri programatori. Aceștia tocmai au terminat un curs de algoritmică si mai avansată în C și încearcă să rezolve probleme cât mai eficient. Una dintre problemele la care se gândesc cei doi spune asta:

• există o matrice $N \times N$ cu valori cuprinse între $0$ și $1$;
• se definește formațiunea de fulg ca fiind un grup de biți care sunt $1$ și pleacă dintr-o celulă pe toate directiile (N, N-E, E, S-E, S, S-V, V, N-V);
• se definește formațiunea de fulg perfect o formă care îndeplinește condiția de fulg dar are și "brațele" aceeași lungime;
• sa se găsească fulgul cel mai lung.

Fulg perfect de lungime 3

1 0 1 0 1
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0
1 0 1 0 1

Fulg perfect de lungime 2

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

Fulg perfect de lungime 1

1 0 1 0 1
0 1 1 0 0
1 1 1 1 1
0 1 1 1 0
1 0 1 0 1

Cum Tudor a găsit din nou soluția optimă, Luca vă plătește să îi rezolvați și lui problema pentru a nu rămâne în urma prietenului său. Vă roagă să fiți foarte atenți datorită limitelor scăzute, cu cât mai ineficienți, cu atât mai puțini bani!!!

Date de intrare

Pe prima linie a fișierului de intrare algoritmul.in se găsesc un număr $N$ și în continuare o matrice de $N \times N$: $a_{11}$, $a_{12}$, $\dots$, $a_{nn}$ reprezentând valoarea de pe pozițiile $a_{ij}$ din matrice.

Date de ieșire

Pe linia $i$ a fișierului de ieșire algoritmul.out se vor găsi $3$ valori, mărimea celui mai mare fulg perfect, iar pe rândul următor coordonatele $(x, y)$ ale centrului acestuia.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• Se acordă 30 de puncte pentru $1 \leq N \leq 300$;
• Se acordă 50 de puncte pentru $1 \leq N \leq 500$;
• Se acordă 80 de puncte pentru $1 \leq N \leq 800$;
• Dacă sunt mai mulți fulgi maxim, afișați-l pe cel cu coordonata $x$ minimă. Dacă sunt mai mulți care respectă și condiția asta, se va afișa cel cu coordonata $y$ minimă.

Exemplu

lumtirogla.in

7
0 1 1 1 0 0 0
0 1 1 1 0 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 1 0 1 0 1 0

lumtirogla.out

3
5 4

Explicație

După cum se vede, există doar $2$ fulgi care au lungimea mai mare de $2$. Primul are centrul în $(2, 3)$ și are mărime $2$. Al doilea are centrul în $(5, 4)$ și are mărime $3$, deci este cel de care avem nevoie.