Cho một ma trận n x m được bao quanh là tường, ở mỗi ô sẽ có một trong các kí tự là ‘S’, ‘.’, ‘C’, ‘L’, ‘R’, ‘U’, ‘D’ và ‘W’:

• ‘S’ là ô mà nhân vật đang đứng và chỉ có một ô có kí tự này.
• ‘.’ là ô bình thường có thể đi vào.
• ‘L’, ‘R’, ‘U’, ‘D’ là các băng chuyền có hướng chuyển động tường ứng với trái, phải, lên, xuống, khi đi vào băng chuyền nhân vật sẽ bị chuyển đến ô khác theo hướng chuyển động của băng chuyền.
• ‘W’ là tường và không thể đi vào ô này.
• ‘C’ là camera có thể quan sát được các ô ở cùng cột và cùng hàng nhưng không thể nhìn qua được tường và không thể thấy các băng chuyền nhưng có thể nhìn qua chúng, các camera chỉ quan sát được và qua được các ô ‘.’, ‘C’ hoặc ‘S’ nếu chúng không bị ngăn cản bởi tường. Khi nhân vật đi đến ô khác sẽ mất chi phí là 1, khi nhân vật đang đứng trên băng chuyền, chúng ta sẽ bị đẩy đến ô khác với chi phí là 0 (vì băng chuyền sẽ tự động di chuyển nhân vật).

Yêu cầu:

In ra tổng chi phí nhỏ nhất để nhân vật đi đến được mỗi ô ‘.’ mà không bị camera phát hiện. Nếu có cách nào để đến được một ô ‘.’ mà không bị phát hiện thì in ra -1.

Input:

• Dòng đầu tiên chứa 2 số nguyên dương n, m (n,m <= 1000) - số hàng và số cột của ma trận.
• n dòng tiếp theo chứa m kí tự thuộc {‘W’, ‘S’, ‘.’, ‘C’, ‘L’, ‘R’, ‘U’, ‘D’} là các ô của ma trận.

Output:

• Gồm k dòng là số lượng ô ‘.’, mỗi dòng là với chi phí nhỏ nhất khi di chuyển từ ô ‘S’ đến ô ‘.’ tương ứng, kết quả in ra theo thứ tự từ trái sang phải, từ trên xuống dưới của các ô.

Ví dụ:

MAZE.INP

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

MAZE.OUT

2
1
3
-1
-1
1