Problem Description

You are given a matrix of size \( R \times C \), composed of characters '', '.', 'D', 'S', and 'X'. The matrix represents a map where '' denotes areas where floodwaters emerge, '.' represents flat land, 'X' is an obstacle that is impassable and impervious to water, 'S' is the starting point from which three hedgehogs (or similar creatures) must reach a shelter, and 'D' marks the shelter. The shelter will not be flooded.

Floodwaters spread to adjacent flat land (four-directionally connected) every unit of time. The hedgehogs can only move on flat land that is not flooded and can move to an adjacent cell (four-directionally connected) every unit of time.

The input consists of the first line containing two integers \( R \) and \( C \) (\( R, C \leq 50 \)), followed by the matrix.

Output the shortest time required for the hedgehogs to reach the shelter, or output "KAKTUS" if it is impossible to reach the shelter.

Input Format

The first line of input contains two integers, \( R \) and \( C \), both less than or equal to 50.
The following \( R \) lines each contain \( C \) characters ('.', '*', 'X', 'D', or 'S'). The map will contain exactly one 'D' character and exactly one 'S' character.

Output Format

Output the shortest possible time needed for the hedgehogs to safely reach the shelter. If this is impossible, output the word "KAKTUS" on a line by itself.

Sample Input and Output

Sample Input #1

3 3
D.*
...
.S.

Sample Output #1

3

Sample Input #2

3 3
D.*
...
..S

Sample Output #2

KAKTUS

Sample Input #3

3 6
D...*.
.X.X..
....S.

Sample Output #3

6

Notes

Clarification of the second sample test: The best path involves moving along the lower border and then the left border, but they get flooded one minute before reaching the den.

见题面 Input 部分

见题面 Output 部分