Bạn được giao nhiệm vụ program một navigation system cho một drone cứu hộ. Drone đã được triển khai trong khu vực thảm họa, có thể được biểu diễn dưới dạng lưới 2D. Nhiệm vụ của bạn là tìm đường đi ngắn nhất có thể cho máy bay không người lái từ vị trí xuất phát đến vị trí của người sống sót.

Lưới chứa các phần tử sau:

• D: Vị trí xuất phát của máy bay không người lái.

• S: Vị trí của người sống sót.

• .: Một đường đi thông thoáng, có thể đi qua.

• #: Một chướng ngại vật hoặc mảnh vỡ không thể vượt qua.

Input

• Dòng đầu tiên chứa hai số nguyên \(R\) và \(C\) được phân cách bằng dấu cách, lần lượt biểu thị số hàng và số cột trong lưới \(1 ≤ R, C ≤ 2000\)
• \(R\) dòng tiếp theo mỗi dòng chứa một chuỗi \(C\) ký tự, biểu thị lưới.

Output:

• Một số nguyên duy nhất biểu thị độ dài của đường đi ngắn nhất từ ​​\(D\) đến \(S\).
• Nếu không có đường đi khả thi đến người sống sót, hãy xuất ra -1.

Example

5 5
D....
###..
..#..
...S.
.....

6