Masala #1139

Xotira 16 MB Vaqt 1000 ms

Virus

Viruslandiyada noma'lum virus tarqalishni boshladi. Bundan xabar topgan Shohruh tezlik bilan o'zini yotoqxonasiga qarab yo'lga chiqdi. Unda Viruslandiya online xaritasi mavjud. Qaysi kvartallarda virus tarqalganligini ko'rishi mumkin. Virus ham tezlik bilan tarqalmoqda. U har soatda o'ziga qo'shni bo'lgan kvartallarni qamrab oladi. Shohruh ham har soatda bir kvartaldan o'ziga qo'shni boshqasiga o'tishi mumkin. Viruslandiya xaritasi \(N \times M\) ko'rnishida.

Bunda Shohruh dastlab turgan kvartal S harfi bilan belgilangan.

Uning yotoqxonasi esa D harfi bilan belgilangan.

Virus aniqlangan hududlar esa yulduzcha(*) bilan belgilangan.

Shuningdek shaharda aholi yashamaydigan kvartallar mavjud bo'lib, u yerda virus tarqala olmaydi va Shohruh ham u yerdan yura olmaydi. U yerlar xaritada X bilan belgilangan.

Shohruh eng kamida necha soatda yotoqxonasiga yetib borishi mumkinligini chop eting. Agar u virus yuqtirib olsa shu zahoti u karantinga olinadi. Bunday holda ″Karantin″ so'zini chop eting.

Qo'shtirnoqsiz va har bir xarf katta kichik ixtiyoriy ko'rinishda.

Kiruvchi ma'lumotlar:

Kirish faylida birinchi qatorda N va M natural sonlari beriladi. Bunda ular 50 dan oshmaydi.

Keyingi N qatorda M tadan belgi kiritiladi. Mos ravishda:

S - Shohruh turgan boshlang'ich kvartal.

D - Shohruhning yotoqxonasi.

* - bular virus tarqalgan hududlar.

. - virus tarqalmagan aholi yashash punktlari.

X - aholi yashamaydigan hududlar

S va D nuqtalar yagona ekanligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida Shohruh eng kamida necha soatda borishini agar borolmasa Karantin so'zini chop eting.

Misollar

#	input.txt	output.txt
1	3 3 D.* ... .S.	3
2	3 3 D.* ... ..S	KARANTIN
3	3 6 D...*. .X.X.. ....S.	6

Izoh:

Virus yotoqxonaga kira olmaydi.