Yo'ldosh, Shavkat va G'iyos nxm lik maydonda ahil yashashardi. Bir kuni Yo'ldosh bilan Shavkat arzimagan narsa ustida tortishib qolishdi. Shavkat maydondan o’ziga tegishli hududni ajratib oldi. Shavkatning hududiga k yoki undan kichik masofagacha yaqin kelish Yo’ldosh uchun juda havfli.  Maydondagi (x₁, y₁) va (x₂, y₂) ikki katak orasidagi masofa sifatida |x₂-x₁|+|y₂-y₁| ga teng. Yo'ldosh Shavkat bilan kelishib olishni muhokama qilish uchun G'iyosning uyiga borish kerak. Yo’ldosh bir urinishda o’zi turgan katakdan qo’shni kataklarning biriga yura oladi. Ikki katak umumiy tamonga ega bo’lsa qo’shni deb aytiladi. Maydonning tashqarisiga chiqib bo’lmaydi va Shavkatning hududiga k yoki undan kichik masofada yaqin bormasligi kerak. Yo'ldoshga bu sharoitda G'iyosning uyiga boradigan eng qisqa yo’lni topishda yordam bering.

Kiruvchi ma’lumotlar

Birinchi qatorda n, m va k sonlari beilgan, n – qatorlar soni, m – ustunlar soni(1≤n,m≤500, 1≤k≤1000). Keyingi n ta qatorda har birida m tadan simvol beriladi. Bo’sh kataklar '.'(nuqta), Shavkatga tegishli kataklar 'S'-harfi, Yo'ldosh turgan katak 'Y' harfi, G'iyos turgan katal 'G' harfi bilan beriladi. Y va G harflari bir martadan uchrashi va Yo'ldosh turgan katak havfli emasli kafolatlanadi.   

Chiquvchi ma’lumotlar

Agar Yo'ldosh Gi'yosning uyiga borib bilmasa -1 chiqaring. Aks holda unga boradigan eng qisqa yo’l uzunligini chiqaring.

Misollar

Tayyorladi: Azat Yusupov