Escape from the Enchanted Forest

The evil emperor Cactus has taken the Magic Keg and flooded the Enchanted Forest! The Painter and the three little hedgehogs must rush to the Beaver's den for safety. The forest is represented as a grid with R rows and C columns. Each cell of the grid can be:

• S: starting position of the Painter and his hedgehogs.
• D: the Beaver's den (the safe destination). Note that water will never flood the den.
• .: an empty field.
• *: a flooded field.
• X: a rock (an impassable obstacle for both water and characters).

Every minute the team can move one step in the 4 cardinal directions (up, down, left, or right). At the same time, the flood expands: every minute, all empty fields adjacent (by side) to a flooded field become flooded. Note that the Painter and hedgehogs cannot move into a cell that is about to be flooded in the same minute.

Your task is to determine the minimum number of minutes required for the Painter and the three little hedgehogs to reach the Beaver's den safely. If it is impossible, output KAKTUS.

Note (Mathematical formulation):

Let \(T_{water}(r,c)\) be the earliest time a cell \((r,c)\) becomes flooded (with \(T_{water}(r,c)=+\infty\) if never flooded) and let \(T_{reach}(r,c)\) be the time when the team reaches that cell. Then for any move into an empty cell (or the starting cell) we require:

[ T_{reach}(r,c) < T_{water}(r,c). ]

The destination cell \(D\) is never flooded.

inputFormat

The first line contains two integers R and C, representing the number of rows and columns in the grid.

Each of the next R lines contains a string of C characters, representing the grid. The characters are one of 'S', 'D', '.', '*', or 'X'.

There is exactly one 'S' and one 'D' in the grid.

outputFormat

Output a single line containing the minimum number of minutes required to reach the Beaver's den. If it is impossible, output KAKTUS.

sample

3 3
S..
...
..D

4