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 đang ấm dần trong hồ (tức là kề cạnh một ô không bị đóng băng) sẽ tan ra.

Thiên nga có thể di chuyển tự do ở những ô chứa nước 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ủa chúng ta 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: '.' (dot) thể hiện 1 ô chứa nước, 'X' thể hiện 1 ô bị đóng băng, và 'L' thể hiện ô có thiên nga. Có chính xác 2 ô chữ L.

Output

• Một dòng duy nhất chứa số ngày đôi thiên nga có thể gặp nhau.

Example

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

3