Tısbağalar və dönmələr
Döyüş tısbağalarını məşq etdirmək üçün hərbçilər w×h ölçüsündə hüceyrələrdən ibarət düzbucaqlı bir poliqon inşa etdilər. Bu poliqonun bəzi hüceyrələri tısbağalar üçün keçilə biləndir, bəziləri isə keçilməzdir. Tısbağalar yalnız poliqonun tərəflərinə paralel hərəkət edə bilərlər. Poliqon elə qurulmuşdur ki, hər hansı bir azad hüceyrədən digərinə çatmaq üçün yalnız bir yol mövcuddur və bu yolda eyni hüceyrədən iki dəfə keçmək olmaz. Tısbağaların düz xətt üzrə sürətli hərəkət etdiyi, lakin 90 dərəcə dönərkən çətinlik çəkdiyi məlumdur. Buna görə də, marşrutun mürəkkəbliyi başlanğıc nöqtəsindən son nöqtəyə keçərkən tısbağanın etməli olduğu dönmə sayına əsasən müəyyən edilir.
Sizdən başlanğıc və son hüceyrələri verilmiş marşrutun mürəkkəbliyini hesablayan bir proqram yazmağınız tələb olunur.
Giriş verilənləri
Birinci sətirdə boşluqla ayrılmış iki tam ədəd h və w, poliqonun ölçüləri (1 ≤ w·h ≤ 100000) verilmişdir. Sonra poliqonun xəritəsi verilir — hər biri w simvoldan ibarət h sətir. "#" simvolu keçilə bilən hüceyrəni, "." isə keçilməz hüceyrəni göstərir. (h+2)-ci sətirdə q, mürəkkəbliyi hesablanmalı olan marşrutların sayı (1 ≤ q ≤ 50000) verilmişdir. Növbəti q sətirdə boşluqla ayrılmış dörd tam ədəd: marşrutun başlanğıc hüceyrəsinin sətir və sütun nömrəsi, marşrutun son hüceyrəsinin sətir və sütun nömrəsi verilmişdir. Başlanğıc və son hüceyrələrin keçilə bilən olduğu təmin edilir. Sətirlər yuxarıdan aşağıya doğru 1-dən h-ə qədər, sütunlar isə soldan sağa doğru 1-dən w-ə qədər nömrələnir.
Çıxış verilənləri
Hər bir marşrut üçün ayrı sətirdə onun mürəkkəbliyini göstərən tək ədəd çıxarın.