Alfa-Zetə Hücum

Kosmik quldur kapitan Kris, uzun müddətdir basqın etməyi planlaşdırdığı yüksək mühafizə olunan süni Alfa-Zet planetinin xəritəsini əldə edib. Məlum olur ki, bütün planet 2D müstəvisində modullarla qurulub və hər biri bir otaq kimi xidmət edir. Hər bir tam ədədi koordinat cütlüyündə dəqiq bir modul var və modulların ölçüsü dəqiq $1\times 1$ vahiddir. Hər modul ən azı bir qonşu modul ilə iki tərəfli əlaqəlidir. Bundan əlavə, istənilən iki modul arasında dəqiq bir yol mövcuddur. Ümumilikdə, modullar döngəsiz düzbucaqlı labirint təşkil edir.

Xəritədə kapitan Kris bir neçə modulu qeyd edib ki, o, məhz bu qaydada ziyarət etmək istəyir. Orada nə edəcəyini sizin işiniz deyil, amma o, sizə marşrut üzrə keçməli olduğu modulların sayını müəyyən etsəniz, böyük bir sərvət vəd edir (döngələr olmadığı üçün o, həmişə bir qeyd olunmuş moduldan növbəti modul üçün birbaşa yolu seçəcək). İlk qeyd olunmuş modul onun səyahətə başladığı yeri, sonuncusu isə bitirmək istədiyi yeri göstərir.

Giriş verilənləri

Birinci sətirdə labirintin hündürlüyü və eni olan iki tam ədəd $h$ və $w(2\le h,w\le 1000)$ verilir.

Sonra labirinti ASCII formatında təsvir edən $h+1$ sətir gəlir, hər sətir $2\cdot w+1$ simvol ehtiva edir. Təsvir həmişə aşağıdakı qaydalara uyğun gəlir:

• Hər tək indeksli sətir və sütunda (indeks $1$-dən başlayaraq) ya şaquli divarlar, ya da boşluqlar var, cüt indeksli sütunlar isə ya üfüqi divarlar, ya da boşluqlar ehtiva edir.

• Birinci sətir labirintin şimal divarını təsvir edir (həmişə yalnız üfüqi divarlardan ibarətdir). Hər növbəti sətir modul sırasını təsvir edir.

• Modul hər cüt indeksli sütunda yerləşir. Onun qərb və şərq divarları müvafiq olaraq dərhal qonşu tək sütun indekslərində yerləşir, şimal divarı isə eyni sütun indeksində, lakin bir sıra yuxarıda yerləşir, cənub divarı isə öz yerindədir. Əgər divar yoxdursa, müvafiq mövqe onun yerinə boşluq ehtiva edir.

Labirint təsvirindən sonra bir tam ədəd $m(2\le m\le 10^4)$ verilir.

Sonrakı $m$ sətirin hər biri iki tam ədəd $x$ və $y(1\le x\le h,1\le y\le w)$ ilə qeyd olunmuş modulu təsvir edir. İlk koordinat cütlüyü səyahətin başlanğıc nöqtəsidir, sonuncu cütlük isə bitiş nöqtəsidir. Modullar bir neçə dəfə görünə bilər, lakin heç vaxt ardıcıl iki və ya daha çox dəfə deyil. $(1,1)$ - yuxarı sol modul, $(h,w)$ - aşağı sağ modul.

Labirintin özünün qapalı olduğu təmin edilir. Üstəlik, istənilən iki modul arasında dəqiq bir yolun mövcudluğu təmin edilir.

Çıxış verilənləri

Bir tam ədəd çıxarın - kapitan Krisin verilən məlumatlara uyğun olaraq marşrutda keçməli olduğu modulların sayı.

Nümunələr