Zadanie

Geológia

Počet bodov: 30

Geológ Martin sa vybral na výpravu za diamantami. Keďže je vyštudovaným geológom, podarilo sa mu nájsť miesto, kde je v zemi diamantov celá kopa! Teraz by z nich chcel vybrať ten najväčší.

K dispozícii máme plánik s diamantami. Diamant má tvar diamantu (štvorca otočeného o \(45\)°). Zem je označená znakom . a okraj diamantu je označený ako #. Keďže diamanty sú priesvitné, vidíme iba ich okraje. Diamanty sa môžu prekrývať.

Vstup a výstup

V prvom riadku sú dve celé čísla \(1 \leq r,s \leq 400\) – počet riadkov a stĺpcov plániku. Nasleduje \(r\) riadkov, kde v každom riadku je \(s\) znakov – buď . alebo #.

Na výstup vypíšte jedno číslo – dĺžku strany najväčšieho diamantu.

Príklady

Input:

5 5
.....
..#..
.#.#.
..#..
.....

Output:

2

Input:

4 3
..#
#..
..#
.#.

Output:

1

Input:

10 10
..#.#.....
.#.#.#....
..#...#...
.#.#...#..
#..#....#.
.#.....#..
..#...#.#.
...#.#...#
.#..#.#.#.
.......#..

Output:

5

Input:

1 1
.

Output:

0