ROdiezv

Se consideră $N$ șiruri de caractere, fiecare șir având lungimea $N$. Șirurile conțin caractere din mulțimea {a, b, ..., z, #}. Putem privi cele $N$ șiruri ca o matrice pătratică de $N \cdot N$ caractere.

Cerință

Să se determine numărul total al romburilor corect formate precum și latura celui mai mare romb care se poate construi în matrice astfel încât acesta să aibă în cele $4$ colțuri caracterul #, fiecare latură a perimetrului rombului să conțină cel puțin o vocală, iar restul caracterelor care alcătuiesc rombul să fie diferite de caracterul #.

Un romb este valid dacă are laturile paralele cu diagonalele matricei și conține cel puțin $13$ elemente pe laturi și în interior.

Exemple de romburi valide (unde $V \in$ {$a$, $e$, $i$, $o$, $u$}, în interiorul romburilor fiind permis orice caracter cu excepția caracterului #):

Date de intrare

Fișierul de intrare rodiezv.in conține pe prima linie numărul natural nenul $N$ cu semnificația din enunț. Pe următoarele $N$ linii, cele $N$ șiruri de caractere.

Date de ieșire

Fișierul de ieșire rodiezv.out va conține două linii. Pe prima linie se află un număr natural nenul ce reprezintă numărul total de romburi corect formate.

Linia a doua conține un număr natural nenul care reprezintă latura celui mai mare romb format care respectă cerință. Se garantează că există cel puțin un romb corect format.

Restricții și precizări

• Cu $M$ vom nota numărul de caractere # din matrice.
• $5 \leq N \leq 2 \ 000$, $4 \leq M \leq 50 \ 000$
• Pentru teste în valoare de $26$ de puncte: $5 \leq N \leq 300$, $4 \leq M \leq 1 \ 000$, matricea nu va conține consoane.
• Pentru alte teste în valoare de $33$ de puncte: $5 \leq N \leq 300$, $4 \leq M \leq 10 \ 000$.
• Pentru alte teste în valoare de $41$ de puncte: Nu există alte restricții.

Exemplu

rodiezv.in

9
ib#addefo
nueaged#s
#etv#m#ce
oawiyacup
ic###awe#
nbaceunoi
f#eiq##eo
oboyhihjn
ioi#etwyi

rodiezv.out

2
3

Explicație

Sunt marcate cele $2$ romburi valide de latură $3$.