Alfa-Zet Basqını#11625
Kosmik quldur, kapitan Kris, yaxınlarda uzun müddət basqın etməyi planlaşdırdığı, ciddi mühafizə olunan süni Alfa-Zet planetinin xəritəsini əldə etmişdir. Məlum oldu ki, bütün planet hər biri ayrıca otaq olan modullardan ibarət ikiölçülü müstəvi kimi qurulub. Hər bir tam ədədi koordinat cütlüyündə dəqiq 1 \times 1 ölçüsündə bir modul yerləşir. Hər bir modul ən azı bir qonşu modul ilə iki tərəfli birləşdirilmişdir. Həmçinin, hər hansı iki modul arasında dəqiq bir yol mövcuddur. Beləliklə, modullar dövrələri olmayan düzbucaqlı labirint yaradır.
Kapitan Kris xəritədə ziyarət etmək niyyətində olduğu bir neçə modulu qeyd etmişdir — məhz verilmiş sıraya uyğun olaraq. Onun orada nə etmək niyyətində olduğu sizi maraqlandırmır, lakin o, sizə kömək edərək marşrut boyunca neçə modulu keçməli olduğunu müəyyən etməyə kömək etsəniz, sizə böyük sərvət vəd edib (çünki dövrələr yoxdur, o, həmişə bir qeyd olunan moduldan növbəti modul üçün ən qısa yolu seçəcəkdir). İlk qeyd olunan modul onun səyahətinin başlanğıcını, sonuncu isə onun sonunu göstərir.
Birinci sətirdə iki tam ədəd və w~(2 \le h, w \le 1000) — labirintin hündürlüyü və eni verilir.
Sonra növbəti h + 1 sətrin labirintin ASCII-sənət formatında təsviri gəlir. Hər bir sətr 2 \cdot w + 1 simvoldan ibarətdir. Təsvir aşağıdakı qaydalara uyğun gəlir:
Hər bir tək cədvəlli sətirdə və sütunda (başlayaraq -dən) şaquli divarlar və ya boşluqlar ola bilər. Cüt indeksli sütunlar üfüqi divarlar və ya boşluqlar ehtiva edir.
Birinci sətr labirintin şimal sərhədini təsvir edir (həmişə yalnız üfüqi divarlardan ibarət olur). Növbəti hər bir sətr ardıcıl üfüqi modul sırasını təsvir edir.
Modul sütunlardakı cüt indeksli mövqelərdə yerləşir. Onun qərb və şərq divarları müvafiq olaraq solda və sağda bitişik tək indekslərdə yerləşir. Şimal divarı eyni sütunda bir sətir yuxarıda, cənub divarı isə eyni sütunda bir sətir aşağıda yerləşir. Divar olmadıqda, yerində boşluq durur.
Labirintin təsvirindən sonra bir tam ədəd m~(2 \le m \le 10^4) — qeyd olunan modulların sayı verilir.
Sonrakı hər bir sətirdə sətir var, hər biri iki tam ədəd və y~(1 \le x \le h, 1 \le y \le w) ehtiva edir — kapitan Krisin ziyarət etmək istədiyi modulun koordinatları. Birinci koordinat cütü səyahətin başlanğıc nöqtəsini, sonuncusu isə sonunu göstərir. Eyni modul bir neçə dəfə rast gələ bilər, lakin heç vaxt ardıcıl iki və ya daha çox dəfə olmaz. Modul labirintin sol üst küncü, isə sağ alt küncüdür.
Zəmanət verilir ki, labirint birləşmişdir. Bundan əlavə, hər hansı iki modul arasında mütləq bir yol mövcuddur.
Bir tam ədəd çıxarın — kapitan Kris göstərilən modullar sırası ilə səyahət edərsə, keçəcəyi ümumi modul sayı.
Nümunə 1
Nümunə 2