Labirint
İran Şahzadəsi gözlərini açdığında, Cəfərin yeraltı labirintinin yuxarı səviyyəsində olduğunu gördü. Labirint, bir-birinin altında yerləşən h səviyyədən ibarətdir. Hər səviyyə m * n ölçülərində düzbucaqlı bir sahəyə bölünmüşdür. Bəzi sahələrdə tavanı dəstəkləyən sütunlar mövcuddur və Şahzadə bu sahələrə daxil ola bilmir.
Şahzadə eyni səviyyədə bir sahədən digərinə keçə bilər, əgər bu sahələr ortaq tərəfə malikdirsə və hər iki sahədə sütun yoxdursa. Bu keçid Şahzadəyə 5 saniyə vaxt aparır.
Cəfərin labirintindəki döşəmələr çox nazikdir və Şahzadə güclü bir ayaq zərbəsi ilə altındakı döşəməni sındıra bilər, əgər alt səviyyədəki müvafiq sahədə sütun yoxdursa. Döşəmə sındıqda, Şahzadə bir səviyyə aşağı düşür, lakin üfüqi müstəvidə yerini dəyişmir. Bu hərəkət də Şahzadəyə 5 saniyə vaxt aparır. Əlbəttə, əgər Şahzadə artıq ən aşağı səviyyədədirsə, onun altındakı döşəmə sındırıla bilməz.
Ən aşağı səviyyədəki bir sahədə, pis Cəfərə ərə getməkdən imtina edən Şahzadə gözləyir. Şahzadəyə, Şahzadəni tapmaq üçün mümkün qədər az vaxt sərf etməyə kömək edin.
Giriş məlumatları
Birinci sətirdə təbii ədədlər h, m və n (2 ≤ h, m, n ≤ 50) - labirintin hündürlüyü və üfüqi ölçüləri verilir. Daha sonra labirintin səviyyələrini yuxarıdan aşağıya doğru təsvir edən h blok verilir.
Hər blokda m sətir var, hər biri n simvoldan ibarətdir: "." (nöqtə) boş sahəni, "o" (kiçik latın hərfi "o") sütun olan sahəni, "1" Şahzadənin səyahətinə başladığı boş sahəni, "2" isə Şahzadənin gözlədiyi boş sahəni göstərir.
Simvollar "1" və "2" dəqiq bir dəfə rast gəlinir: "1" simvolu ən yuxarı səviyyənin təsvirində, "2" simvolu isə ən aşağı səviyyənin təsvirində.
Yandakı bloklar bir boş sətirlə ayrılır.
Çıxış məlumatları
Şahzadənin Şahzadəni tapması üçün lazım olan minimal vaxtı saniyə ilə göstərin. Çünki Yaxşılıq həmişə Şərə qalib gəlir, Şahzadənin bunu edə biləcəyi təmin edilir.