labudovi

문제

Two swans are living on a lake but they are separated with ice that covers parts of the lake. 

Lake is rectangular in shape and consists of squares arranged in R rows and C columns. Some squares are covered with ice. 

Lake is gradually defrosting – in one day all of the squares covered with ice that are in touch with water melt and turn into water. We consider two squares to be in touch if they are neighbors horizontally or vertically (but not diagonally). 

The following figure depicts the lake from the third example: 

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
in the beginning   after first day   after second day 

Swans can move only on water squares in horizontal and vertical (but not diagonal) direction. 

Write a program that will calculate after how many days the swans will be able to meet each other. 

입력

First line of input contains two integers R and C, 1 ≤ R, C ≤ 1500. 

Each of the following R lines contains a sequence of C characters, the description of the lake at the beginning: '.' (dot) denotes a water square, 'X' denotes an ice-covered square, and 'L' denotes a square with a swan.

출력

First and only line of output should contain the number of days from the problem statement. 

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

3

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

2

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

2