Hồ thiên nga

Hai con thiên nga đang ở trong một cái hồ lớn, nhưng chúng lại đang bị chia cắt bởi băng đóng trong hồ nước. Hồ nước có dạng hình chữ nhật được chia thành \(r\) dòng, \(c\) cột. Một số ô trong hồ bị băng đóng. Mùa xuân tới dần, băng trong hồ tan dần: mỗi ngày, băng ở tất cả những ô tiếp xúc với nước (tức là kề cạnh với một ô không bị đóng băng) sẽ tan ra.

Thiên nga có thể di chuyển tự do giữa các ô chứa nước kề cạnh nhau nhưng không thể đi qua những ô bị đóng băng. Bạn hãy tính xem sau bao nhiêu ngày thì đôi thiên nga có thể gặp nhau.

Input

• Dòng đầu tiên chứa \(2\) số \(r\) và \(c\) (\(1 \le r, c \le 1500\)).
• Mỗi dòng trong \(r\) dòng tiếp theo chứa \(c\) kí tự mô tả hồ nước tại thời điểm hiện tại: . thể hiện ô chứa nước, X thể hiện ô bị đóng băng, và L thể hiện ô có thiên nga (ô có thiên nga là ô nước). Có chính xác \(2\) ô chữ L.

Output

Một dòng duy nhất chứa số ngày ít nhất để đôi thiên nga có thể gặp nhau (nếu ngay từ đầu chúng đã gặp được nhau thì in ra \(0\)).

Sample Input 1

10 10
XXL.XXX.XX
XXXXXXXXXX
XXXXXXXXX.
XXXXXXXXXX
.XXXXXXXXX
L.XXXXXXXX
XXX.XXXXX.
XXXXXXXXXX
XXXXXXXXXX
XXXX.XXX.X

Sample Output 1

2