Ой усанд автжээ. Аялагч агуй руугаа буцах ёстой бөгөөд ингэснээр аюулгүй болно. Ойн газрын зураг нь R мөр, С баганаас бүрдэнэ. Хоосон талбарыг '.' тэмдгээр, үерт автсан талбарыг '*', хадыг 'X'-ээр тэмдэглэсэн. Нэмж дурдахад агуйг "D" болон аялагчийг "S" гэж тэмдэгдэсэн байдаг. Мөч тутамд аялагч өөрийн байгаа талбарын 4 хөрш зэргэлдээх талбар руу (дээш, доош, зүүн, баруун) шилжиж болно. Гачлантай нь мөч тутам үер ихсэж, үерт автсан талбартай дор хаяж нэг нийтлэг талтай бүх хоосон талбарууд үерт автдаг. Үерийн ус дамжин дамж урсахгүй. Аялагч мөн хадыг давж чадахгүй бас тэрээр үерт автсан талбарыг дайран өнгөрч чадахгүй. Агуйн усанд автахгүй. Ойн газрын зургийг өгснөөр аялагчийг агуйд аюулгүй хүргэх хамгийн богино хугацааг тодорхойлох программ бичнэ үү.

Input Format

Оролтын эхний мөрөнд 50-аас хэтрэхгүй хоёр бүхэл тоо R ба C байна. Дараах R мөрөнд C тэмдэгт ('.', '*', 'X', 'D' эсвэл 'S') орно. Газрын зураг нь яг нэг 'D' тэмдэгт ба яг нэг 'S' тэмдэгтийг агуулна.

Constraints

• \(0< r,c<= 50\)

Output Format

Аялагч агуйд аюулгүй очиход шаардагдах хамгийн богино хугацааг гаргана. Хэрэв энэ боломжгүй бол "KAKTUS" гэсэн үгийг нэг мөрөнд бичнэ үү.

Оролт-1

3 3
D.*
...
.S.

Гаралт-1

3

Оролт-2

3 3
D.*
...
..S

Гаралт-2

KAKTUS

Оролт-3

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

Гаралт-3

6