Hoàng đế độc ác Cactus đã sở hữu Thùng rượu Ma thuật và đã làm ngập khu rừng Mộng Mơ. Họa sĩ và ba chú nhím nhỏ bây giờ phải quay trở về hang của Hải ly, nơi họ sẽ được an toàn càng nhanh càng tốt.

Bản đồ của khu rừng Mộng mơ bao gồm ~R~ hàng và ~C~ cột. Các khu vực trống được biểu diễn bằng ký tự '.', các khu vực bị ngập là '*' và các tảng đá là 'X'. Ngoài ra, hang Hải ly được biểu diễn bằng ký tự 'D' và Họa sĩ các 3 chú nhím nhỏ là 'S'.

Mỗi phút Họa sĩ và các chú nhím có thể di chuyển một trong 4 hướng (lên, xuống, trái, phải). Mỗi phút, lũ lụt cũng sẽ lan ra các khu vực trống liền kề ngay cạnh ô bị ngập. Họa sĩ và nhím không thể vượt qua các khu vực bị đá chắn đường. Tương tự, họ cũng không thể vượt qua các khu vực bị ngập, và hang Hải ly thì cũng không thể bị ngập.

Bạn hãy viết một chương trình, từ bản đồ của rừng Mông Mơ, hãy đưa ra thời gian ngắn nhất cho Họa sĩ và 3 chú nhím có thể đến hang Hải ly một cách an toàn.

• Lưu ý: Họa sĩ và 3 chú nhím không thể di chuyển vào một khu vực sắp bị ngập (trong cùng một phút).

Input

• Dòng đầu tiên gồm 2 số nguyên ~R~ và ~C~ (R, C <= 50).
• R dòng tiếp theo, mỗi dòng gồm ~C~ ký tự ('.', '*', 'X', 'D' hoặc 'S'). Bản đồ sẽ chỉ gồm duy nhất một ký tự 'D' và một ký tự 'S'.

Output

In ra thời gian nhỏ nhất có thể để Họa sĩ và nhóm nhỏ có thể đến hang Hải ly một cách an toàn. Nếu không có phương án khả thi, hãy in ra "KAKTUS".

Sample input 1

3 3 
D.* 
... 
.S.

Sample output 1

3

Sample input 2

3 3 
D.* 
... 
..S

Sample output 2

KAKTUS