+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در جلسه‌ای بین هیات مدیره‌ی شرکت اسنپ، مدیران فریاد «ما پویا هستیم» سر دادند و تصمیم گرفتند کسب و کار شرکتشان را گسترش دهند و علاوه بر داخل شهرها، در دریا هم به مشتریانشان خدمت‌رسانی کنند. به همین جهت تعدادی قایق‌ران استخدام کردند تا به رفت و آمد مسافران بین جزایر کمک کنند. در نگاه اوّل این طرح بسیار خوب به نظر می‌آمد، امّا پس از مدّتی مسافران متوجّه شدند که تمام سیستم‌های مسیریابی موجود برای داخل شهر ساخته شده‌اند و سیستم مناسبی برای یافتن مسیر بهینه در دریا وجود ندارد. افراد تیم فنّی تصمیم گرفتند خودکفا باشند، لذا فریاد «ما می‌توانیم» سر دادند و خود شروع به طرّاحی چنین سیستمی کردند. امّا آیا واقعا می‌توانستند؟ ما را در ادامه‌ی این سوال همراهی کنید تا پاسخ این پرسش را بیابیم... دریا به شکل یک مستطیل با $h$ سطر و $w$ ستون است(متشکّل از $h.w$ خانه به شکل مربّع $1\times 1$). هر یک از جزایر نیز زیر مستطیل‌هایی از دریا را اشغال می‌کنند که اضلاعشان موازی اضلاع آن است؛ هم‌چنین هر خانه از دریا یا به طور کامل در یک جزیره قرار دارد یا به طور کامل خارج از آن است. قایق در هر خانه که باشد، در ثانیه‌ی بعد می‌تواند به یکی از خانه‌های مجاور ضلعی آن خانه برود؛ شاید باورتان نشود ولی حتّی اگر این خانه‌ها در خشکی باشند، قایق‌های اسنپ توانایی حرکت در آن‌ها را دارند. (مدیران هنگام آغاز طرح، فریاد «ما وسایل نقلیه‌ی خاصی داریم» نیز سر داده بودند) مسافران از رفت و آمد درون دریا متنفّر هستند! پس سیستم مسیریابی باید به ازای تعدادی درخواست شامل یک مبدا و مقصد مشخّص، بگوید کم‌ترین تعداد خانه‌های داخل دریا که باید طی شوند تا از آن مبدا به آن مقصد برسیم چند تاست. افراد تیم فنّی که در حال بررسی این سیستم بودند، پس از چند روز تفکّر، فریاد «ما خیلی خفنیم... این سوال بیش از حد بدیهیه» سر دادند و از ما خواستند که شرکت کنندگان **اسنپ چلنج** این سوال را حل کنند. لذا ما ابعاد جدول و مکان جزیره‌ها را به شما می‌دهیم و می‌خواهیم برنامه‌ای بنویسید که به ازای تعدادی درخواست، جواب مطلوب مسافران -که همانا حداقل تعداد خانه‌های طی شده شامل آب برای رسیدن از مبدا به مقصد است- را به دست آورد. مبدا و مقصدهای داده شده صرفا خانه‌هایی داخل دریا هستند و ممکن است درون یک جزیره و یا خارج از تمام جزایر باشند. برای سهولت در ورودی دادن، سطر‌های دریا را از بالا به پایین با ۱ تا $h$ و ستون‌هایش را به ترتیب از چپ به راست با ۱ تا $w$ شماره‌گذاری کرده‌ایم. برای نشان‌دادن خانه‌ی سطر ‌$i$ام و ستون $j$ام، از دوتایی $i j$ استفاده می‌کنیم. # ورودی در ورودی استاندارد، ابتدا به ترتیب سه عدد $h$ و $w$ و $n$ (تعداد جزایر) داده می‌شود. در هر یک از $n$ خط بعد چهار عدد داده می‌شود: به ترتیب $x1$ و $y1$ و $x2$ و $y2$ که نمایانگر خانه‌های دو گوشه‌ی مخالف از جزیره‌ی ‌$i$ام هستند. در خط $n+2$ عدد $q$ داده می‌شود. در ادامه $q$ خط وجود خواهد داشت که در $i$امین خط از آن‌ها، مشخصات درخواست $i$ام داده می‌شود. مشخصات هر درخواست، شامل مختصات خانه‌ی مبدا و خانه‌ی مقصد با قالب گفته شده خواهد بود، یعنی اعداد $x1$ و $y1$ و $x2$ و $y2$ با همین ترتیب داده می‌شوند؛ $x1 y1$ مختصات مبدا و $x2 y2$ مختصات خانه‌ی مقصد خواهد بود. $$1 \le n \le 100$$ $$1 \le q \le 200$$ $$1 \le h, w \le 10^9$$ تضمین می‌شود که هر نقطه اگر روی محیط یک جزیره نباشد، داخل حداکثر یک جزیره است. # خروجی در خروجی باید $q$ خط چاپ کنید. در خط $i$ام جواب درخواست $i$ام را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 2 1 1 1 1 3 3 3 3 2 1 3 3 1 1 2 1 3 ``` ## خروجی نمونه ۱ ``` 4 2 ```  ## ورودی نمونه ۲ ``` 6 5 4 1 2 1 3 3 1 4 2 3 4 5 4 6 2 6 2 5 1 1 6 5 3 2 3 4 3 3 3 4 3 1 4 2 1 5 6 5 ``` ## خروجی نمونه ۲ ``` 5 1 1 0 5 ``` 

حل سؤال در بانک سؤالات