Zindan Divarı#3544
2337-ci ildə insanlar gündəlik həyatdan beziblər və qeyri-adi təcrübələr axtarırlar. Bu günlərdə "Zindan Macərası" ən populyar əyləncələrdən biridir, burada cəsur macəraçılar həyatlarını təhlükəyə ataraq pis canavarları məhv edir və dünyanı xilas edirlər.
Siz belə zindanlardan birinin menecerisiniz. Son zamanlarda zindana tez-tez girən əsgərlərdən çoxlu şikayətlər alırsınız; onlar zindanınızın çox asan olduğunu və yenidən girmək istəmədiklərini deyirlər. Siz zindanınızı daha çətin etmək üçün giriş və çıxış arasındakı məsafəni artırmağı düşünürsünüz ki, daha çox canavar macəraçılara yaxınlaşa bilsin.
Zindanınızın forması, eni və hündürlüyü olan düzbucaqlıdır. Zindan W \times H ölçüsündə eyni ölçülü 1 \times 1 kvadrat otaqlardan ibarət şəbəkədir. Zindanın cənub-qərb küncü koordinat , şimal-şərq küncü isə (W, H) koordinatında yerləşir. Zindanın xarici hissəsi divarlarla əhatə olunub və macəraçıların birbaşa çıxışa getməsinin qarşısını almaq üçün zindanın içində də əlavə divarlar ola bilər. Hər bir divar ya oxuna, ya da oxuna paraleldir və hər bir divarın iki ucu tam ədədi koordinatlarda yerləşir. Macəraçı bir otaqdan digər otağa şaquli və ya üfüqi olaraq keçə bilər, əgər aralarında divar yoxdursa.
Siz giriş və çıxış arasındakı ən qısa yolu uzatmaq üçün divar əlavə etmək istəyirsiniz. Lakin, maliyyə məhdudiyyətləri yalnız bir vahid uzunluqda divar tikməyə imkan verir. Yeni divar da yuxarıda göstərilən məhdudiyyətlərə uyğun olmalıdır. Bundan əlavə, girişdən çıxışa ən azı bir yolun olması təmin edilməlidir.
Siz düşünürsünüz ki, giriş və çıxış arasındakı minimum addım sayını maksimum artırmaq üçün yeni divarı harada yerləşdirməlisiniz? Bunu tapa bilərsinizmi?
Birinci sətir üç tam ədəd ehtiva edir: , və (1 \leq W, H \leq 50, 0 \leq N \leq 1000). Onlar boşluqla ayrılıb.
Növbəti sətir zindanın içindəki divarın spesifikasiyalarını verir. Hər bir divar spesifikasiyası dörd tam ədəd ehtiva edir: sx_i, sy_i, dx_i, dy_i — -ci divarın son nöqtələri, (sx_i, sy_i)-dən (dx_i, dy_i)-yə qədər (daxil olmaqla).
Son iki sətir giriş və çıxışın yerləri haqqındadır. Birinci sətir iki tam ədəd və ehtiva edir, ikinci isə iki tam ədəd və . Giriş, cənub-qərb küncü (ix, iy) olan otaqda yerləşir və çıxış, cənub-qərb küncü (ox, oy) olan otaqdadır.
Yalnız bir divar əlavə etməklə giriş və çıxış arasında tələb olunan minimum addım sayının mümkün maksimum artımını çap edin. Əgər yeni divar tikmək üçün uyğun yer yoxdursa, 0 çap edin.
Nümunə 1