邪恶的皇帝 Cactus 拥有一只魔法桶，并用它淹没了魔法森林！画家和三只小刺猬现在必须尽快回到海狸的巢穴，在那里他们才能安全地躲避洪水！

魔法森林的地图由 $R$ 行 and $C$ 列组成。空地用字符 . 表示，被水淹没的区域用 * 表示，岩石用 X 表示。此外，海狸的巢穴用 D 表示，画家和三只小刺猬的起始位置用 S 表示。

每一分钟，画家和三只小刺猬可以移动到相邻的 4 个格子（上、下、左、右）之一。同时，每一分钟洪水也会蔓延，所有与已被淹没的格子至少共享一条公共边的空地都会被水淹没。水和画家及小刺猬都无法穿过岩石。自然地，画家和三只小刺猬不能穿过已被淹没的区域，而水也不能淹没海狸的巢穴。

编写一个程序，在给定魔法森林地图的情况下，输出画家和三只小刺猬安全到达海狸巢穴所需的最短时间。

注意：画家和三只小刺猬不能移动到在同一分钟内即将被淹没的格子里。

输入格式

输入的第一行包含两个整数 $R$ 和 $C$，它们均小于或等于 50。

接下来的 $R$ 行，每行包含 $C$ 个字符（.、*、X、D 或 S）。地图中将恰好包含一个 D 字符和一个 S 字符。

输出格式

输出画家和三只小刺猬安全到达海狸巢穴所需的最短时间。如果这是不可能的，则单行输出单词 KAKTUS。

样例

输入格式 1

3 3
D.*
...
.S.

输出格式 1

3

输入格式 2

3 3
D.*
...
..S

输出格式 2

KAKTUS

说明

他们能做的最好的选择是沿着下边界走，然后沿着左边界走，但在到达巢穴前一分钟就会被洪水淹没。

输入格式 3

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

输出格式 3

6