careu

Gigel a inventat un nou joc, de această dată utilizând un rebus sub forma de tablă pătratică cu $N \times N$ căsuțe. Fiecare căsuță conține câte o literă mare din alfabetul englez sau caracterul .. Literele formează pe orizontală sau pe verticală cuvinte delimitate prin caractere punct sau prin marginile tablei. Cel care joacă trebuie să determine cuvintele speciale din careu. Punctajul unui cuvânt se calculează ca suma codurilor ASCII ale literelor distincte care apar în acel cuvânt. Punctajul total al jocului se calculează însumând punctajele literelor distincte ale cuvintelor speciale distincte. Un cuvânt special îndeplinește simultan condițiile:

• este palindrom
• are lungime maximă relativ la alte cuvinte palindrom

Cerință

Să se scrie un program care sa determine, pentru un careu dat, punctajul maxim și cuvintele care permit obținerea punctajului maxim. Dacă nu există astfel de cuvinte se va afișa valoarea $0$.

Date de intrare

Fișierul de intrare careu.in conține pe prima linie un număr natural $n$ reprezentând dimensiunea careului. Următoarele $n$ linii conțin fiecare câte $n$ caractere, neseparate prin spații, reprezentând careul. Ultima linie a fișierului de intrare conține una dintre valorile $1$ sau $2$ reprezentând cerința.

Date de ieșire

Fișierul de ieșire careu.out conține pentru cerința $1$, pe prima linie numărul de cuvinte speciale de valoare maximă găsite, iar pe următoarele linii se vor scrie aceste cuvinte în ordine alfabetică, câte unul pe linie; pentru cerința $2$, pe prima linie a fișierului de ieșire se va scrie punctajul maxim determinat.

Restricții și precizări

• $2 \leq n \leq 50$
• Cuvintele sunt scrise cu litere mari și lungimea cuvintelor din soluție trebuie să fie cel puțin $2$
• Pentru cerința $1$ se acordă $60\%$ din punctaj, iar pentru cerința $2$ se acordă $30\%$ din punctaj
• $10$ puncte se acordă din oficiu

Exemplul 1

careu.in

3
A.A
B.A
..C
1

careu.out

0

Explicație

Nu există nici un cuvânt special de lungime $\geq 2$

Exemplul 2

careu.in

10
VERDE.CRIN
DANA.DDDDD
VOI.AOQOA.
NU.AAOTE..
.UBOBU.AIA
EZNGAIETAR
ORIOATZULI
TURN.NNNNN
O.ZZCZZ.IU
ELEGATEL.O
1

careu.out

8
AABAA
AOQOA
DDDDD
EOTOE
EZNZE
NNNNN
UBOBU
ZZCZZ

Explicație

Cerința $1$. Au fost determinate $8$ cuvinte speciale

Exemplul 3

careu.in

10
VERDE.CRIN
DANA.DDDDD
VOI.AOQOA.
NU.AAOTE..
.UBOBU.AIA
EZNGAIETAR
ORIOATZULI
TURN.NNNNN
O.ZZCZZ.IU
ELEGATEL.O
2

careu.out

832

Explicație

Cerința $2$. Punctajul maxim pentru cele $8$ cuvinte speciale este $832 = 65+66+67+68+69+78+79+81+84+85+90$