Problem Description

You are given a $n \times n$ map, where each cell is either a . or an X.

Determine the largest $k$ such that:

On the map, you can find $m$ (where $m \leq 2$) non-overlapping strips of size $1 \times k$ or $k \times 1$ that consist entirely of ..

Input Format

The first line contains two positive integers $n$ and $m$.

The next $n$ lines describe the map.

Output Format

Output a single non-negative integer, the largest possible $k$.

Sample Input and Output

Input Sample #1

5 2
.X...
.XXXX
XX...
.....
.X.X.

Output Sample #1

3

Input Sample #2

2 1
..
..

Output Sample #2

2

Input Sample #3

2 2
X.
..

Output Sample #3

1

Input Sample #4

10 2
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
..........
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

Output Sample #4

5

Input Sample #5

10 2
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X

Output Sample #5

10

Input Sample #6

(Refer to the attachment)

Output Sample #6

531

Notes

For all test cases, $1 \leq n \leq 1500$, $1 \leq m \leq 2$, and the map consists only of . and X.

见题面 Input 部分

见题面 Output 部分