Background

Special for beginners, ^_^

Description

邪恶的国王凯克特丝有一个魔法水桶，魔法水桶可以让水泛滥淹掉一切。善良的皮特与三个小刺猬一定要在洪水来到前逃到海狸的宫殿中。 R行C列的字符构成了魔幻地图：其中“.”表示空地；“*”表示魔法水桶所在位置；大写字母“X”表示岩石；大写字母“D”表示海狸的宫殿，而皮特与三个刺猬从发地用大写字母“S”表示。 每个时刻皮特与三个刺猬都有可以移动到四个方向（上、下、左、右）。每个时刻魔法水桶都让水淹没四周的空地（就是每次洪水上涨淹掉四周一圈空地）。皮特和三个刺猬既不能走过洪水区，也不能走过岩石。当然洪水是不能淹掉海狸的宫殿的。 写一个程序，在所给的地图中找出皮特与三个小刺猬逃到海狸的宫殿的最短时间。注意的是在同一个时刻他们不能移到洪水也漫到的地方。

Format

Input

输入文件slikar.in中第一行：输入地图的R，C它们均小等于50；接下来的R行C列由字符“.” “*” “X” “D” “S”组成。.

Output

输出文件slikar.in中仅一行：如果皮特与三个小刺猬能安全到达海狸的宫殿，则输出最短时间；否则输出大写单词“KAKTUS”.

Samples

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

6

Limitation

1s, 1024KiB for each test case.