Bajtazar is currently developing a plan for a new airport to be built in the center of Byteotia. The airport occupies an $n \times n$ square of "bytemeters" and is divided on the plan into $n^2$ fields of $1 \times 1$ bytemeters. Some of the fields are already occupied by planned buildings (departure and arrival hall, control tower, hangars). Bajtazar's task is to plan space for $m$ ($m \le 2$) runways of the same length.
Each runway of length $k$ must consist of $k$ adjacent empty fields, forming a rectangle of $1 \times k$ or $k \times 1$ bytemeters. The runways must be disjoint (in the case of $m = 2$) and cannot contain any occupied fields. Bajtazar is wondering what the maximum length of the runways that can fit on the airport is.
Input
The first line of input contains two integers $n$ and $m$ ($1 \le n \le 1500$, $1 \le m \le 2$), representing the side length of the airport and the number of runways to be built.
The next $n$ lines contain the description of the airport; each of them contains an $n$-letter word consisting of the characters X (occupied field) or . (empty field).
Output
In the only line of output, print a single integer $k$ representing the maximum length of the runways that can be planned.
Examples
Input 1
5 2 .X... .XXXX XX... ..... .X.X.
Output 1
3
Note
Explanation of the example: The following drawing shows a possible placement of runways of length 3:
.X... .XXXX XX..2 111.2 .X.X2
Subtasks
| Subtask | Constraints | Points |
|---|---|---|
| 1 | $m = 1$ | 20 |
| 2 | $n \le 30$ | 22 |
| 3 | $n \le 300$ | 23 |
| 4 | $n \le 1500$ | 35 |