Bạn bị lạc vào một mê cung được mô tả bằng một lưới kích thước ~m \times n~, mỗi ô của lưới chứa một trong ba loại kí tự sau:

• Kí tự "W": phòng chưa tường không đi vào được;
• Kí tự ".": phòng trống đi vào được;
• Các kí tự "U"/ "L"/"D"/"R": phòng chứa băng trượt, khi di chuyển vào phòng đó ngay lập tức bạn bị đẩy sang phòng tương ứng bên trên/bên trái/bên dưới/bên phải của phòng đó (nếu ô tương ứng là ô tường bạn sẽ ở lại ô trượt đó mãi mãi).
• Kí tự "C": phòng có một lính canh, lính canh sẽ quan sát được các phòng cùng hàng hoặc cùng cột nếu giữa phòng đó và phòng mà lính canh đứng không có phòng chứa tường nào, nhưng lính canh sẽ không kịp quan sát thấy bạn khi bạn di chuyển vào phòng chứa băng trượt.
• Kí tự "S": phòng mà bạn đang đứng. Mỗi đơn vị thời gian, bạn được lựa chọn di chuyển sang một ô chung cạnh. Nếu di chuyển vào ô chứa băng trượt ngay lập tức bạn sẽ bị đẩy sang ô tương ứng. Để lên kế hoạch thoát khỏi mê cung, bạn muốn tính thời gian ngắn nhất để di chuyển từ ô đang đứng tới từng ô trống trong mê cung.

Input

• Dòng đầu chứa hai số nguyên dương ~m, n~ ~(m,n≤1000)~;
• Tiếp theo là ~m~ dòng, mỗi dòng chứa ~n~ số mô tả mê cung.

Output

• Gọi ~k~ là số phòng trống trong cung. Ghi ra file gồm ~k~ dòng là thời gian ngắn nhất di chuyển từ ô đang đứng tới từng ô trống trong mê cung theo thứ tự các ô từ trên xuống dưới, từ trái sang phải.

Sample Input

5 7
WWWWWWW
WD.L.RW
W.WCU.W
WWW.S.W
WWWWWWW

Sample Output

2
1
3
-1
-1
1

Giới hạn

• Subtask 1: Mê cung không có lính canh và không có ô trượt;
• Subtask 2: Mê cung không có ô trượt;
• Subtask 3: Không có giới hạn nào thêm.