Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Xe buýt là một trong những giải pháp giao thông tốt hiện nay. Bên cạnh đa số những cá nhân cư xử văn minh, vẫn có những hành động không đẹp xảy ra. Đó là vấn đề tranh chỗ ngồi trên xe buýt.

Khi có ghế trống trên xe buýt, một số người khiếm nhã sẽ cố gắng chạy thật nhanh tới vị trí đó để chiếm chỗ ngồi. Nếu có nhiều ghế trống, họ sẽ tìm chiếc ghế gần nhất.

Vấn đề sẽ phát sinh nếu có nhiều hơn 2 người cho một mục tiêu ghế trống. Nếu một trong 2 người ở gần chiếc ghế trống hơn, người đó sẽ chạy đến và giữ chỗ, trong khi đó người còn lại biết mình không thể cạnh tranh vị trí đó, sẽ chuyển sang tìm kiếm một mục tiêu mới. Nhưng trong trường hợp khoảng cách của 2 người tới chiếc ghế là bằng nhau, cả 2 sẽ đâm đầu mà chạy, kết quả là sẽ xảy ra vụ va chạm lớn trên xe buýt.

Xe buýt được mô tả bằng một bảng R x C, gồm R hàng và C cột. Những hành khách khiếm nhã được đánh dấu là ‘X’, những chiếc ghế trống được đánh dấu là ‘L’, sàn xe buýt là ‘.’.

Mặc dù có thể có hành khách cản trở đường đi, nhưng những người khiếm nhã này sẽ cố gắng nhảy qua tất cả, để đi theo đường chim bay tới đích.

Khoảng cách giữa 2 vị trí được tính theo khoảng cách Ơ - clit. Nhiệm vụ của các bạn là viết chương trình xác định số va chạm sẽ xảy ra.

Input

Dòng đầu tiên gồm 2 số nguyên R và C là kích thước của xe buýt, (1 ≤ R ≤ 100) and C (1 ≤ C ≤ 100), tương ứng số hàng và số cột.

R dòng tiếp theo, mỗ dòng chứa C kí tự, bao gồm các kí tự ‘.’, ‘X’, hoặc ‘L’.

Luôn có ít nhất một kí tự ‘X’ và ít nhất một kí tự ‘L’. Và không có trường hợp nào có 2 ghế trống ‘L’ mà khoảng cách của chúng tới một số hành khách ‘X’ là bằng nhau.

Output

In ra một số nguyên dương duy nhất là số va chạm sẽ xảy ra.

Example

Test 1:

Input:

4 4
.LX.
.X..
....
.L..

Output:

1

Test 2:

Input:

4 4
.XLX
.X..
...L
.X..

Output:

2

Test 3:

Input:

7 7
...X.X.
XL....L
.......
...L...
.....XL
.......
...X...

Output:

1