فریاد


  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

در جلسه‌ای بین هیات مدیره‌ی شرکت اسنپ، مدیران فریاد «ما پویا هستیم» سر دادند و تصمیم گرفتند کسب و کار شرکتشان را گسترش دهند و علاوه بر داخل شهرها، در دریا هم به مشتریانشان خدمت‌رسانی کنند. به همین جهت تعدادی قایق‌ران استخدام کردند تا به رفت و آمد مسافران بین جزایر کمک کنند.

در نگاه اوّل این طرح بسیار خوب به نظر می‌آمد، امّا پس از مدّتی مسافران متوجّه شدند که تمام سیستم‌های مسیریابی موجود برای داخل شهر ساخته شده‌اند و سیستم مناسبی برای یافتن مسیر بهینه در دریا وجود ندارد. افراد تیم فنّی تصمیم گرفتند خودکفا باشند، لذا فریاد «ما می‌توانیم» سر دادند و خود شروع به طرّاحی چنین سیستمی کردند.

امّا آیا واقعا می‌توانستند؟ ما را در ادامه‌ی این سوال همراهی کنید تا پاسخ این پرسش را بیابیم...

دریا به شکل یک مستطیل با hh سطر و ww ستون است(متشکّل از h.wh.w خانه به شکل مربّع 1×11\times 1). هر یک از جزایر نیز زیر مستطیل‌هایی از دریا را اشغال می‌کنند که اضلاعشان موازی اضلاع آن است؛ هم‌چنین هر خانه از دریا یا به طور کامل در یک جزیره قرار دارد یا به طور کامل خارج از آن است.

قایق در هر خانه که باشد، در ثانیه‌ی بعد می‌تواند به یکی از خانه‌های مجاور ضلعی آن خانه برود؛ شاید باورتان نشود ولی حتّی اگر این خانه‌ها در خشکی باشند، قایق‌های اسنپ توانایی حرکت در آن‌ها را دارند. (مدیران هنگام آغاز طرح، فریاد «ما وسایل نقلیه‌ی خاصی داریم» نیز سر داده بودند) مسافران از رفت و آمد درون دریا متنفّر هستند! پس سیستم مسیریابی باید به ازای تعدادی درخواست شامل یک مبدا و مقصد مشخّص، بگوید کم‌ترین تعداد خانه‌های داخل دریا که باید طی شوند تا از آن مبدا به آن مقصد برسیم چند تاست.

افراد تیم فنّی که در حال بررسی این سیستم بودند، پس از چند روز تفکّر، فریاد «ما خیلی خفنیم... این سوال بیش از حد بدیهیه» سر دادند و از ما خواستند که شرکت کنندگان اسنپ چلنج این سوال را حل کنند. لذا ما ابعاد جدول و مکان جزیره‌ها را به شما می‌دهیم و می‌خواهیم برنامه‌ای بنویسید که به ازای تعدادی درخواست، جواب مطلوب مسافران -که همانا حداقل تعداد خانه‌های طی شده شامل آب برای رسیدن از مبدا به مقصد است- را به دست آورد.

مبدا و مقصدهای داده شده صرفا خانه‌هایی داخل دریا هستند و ممکن است درون یک جزیره و یا خارج از تمام جزایر باشند.

برای سهولت در ورودی دادن، سطر‌های دریا را از بالا به پایین با ۱ تا hh و ستون‌هایش را به ترتیب از چپ به راست با ۱ تا ww شماره‌گذاری کرده‌ایم. برای نشان‌دادن خانه‌ی سطر ‌iiام و ستون jjام، از دوتایی iji j استفاده می‌کنیم.

ورودی🔗

در ورودی استاندارد، ابتدا به ترتیب سه عدد hh و ww و nn (تعداد جزایر) داده می‌شود.

در هر یک از nn خط بعد چهار عدد داده می‌شود: به ترتیب x1x1 و y1y1 و x2x2 و y2y2 که نمایانگر خانه‌های دو گوشه‌ی مخالف از جزیره‌ی ‌iiام هستند.

در خط n+2n+2 عدد qq داده می‌شود.

در ادامه qq خط وجود خواهد داشت که در iiامین خط از آن‌ها، مشخصات درخواست iiام داده می‌شود. مشخصات هر درخواست، شامل مختصات خانه‌ی مبدا و خانه‌ی مقصد با قالب گفته شده خواهد بود، یعنی اعداد x1x1 و y1y1 و x2x2 و y2y2 با همین ترتیب داده می‌شوند؛ x1y1x1 y1 مختصات مبدا و x2y2x2 y2 مختصات خانه‌ی مقصد خواهد بود.

1n1001 \le n \le 100 1q2001 \le q \le 200 1h,w1091 \le h, w \le 10^9

تضمین می‌شود که هر نقطه اگر روی محیط یک جزیره نباشد، داخل حداکثر یک جزیره است.

خروجی🔗

در خروجی باید qq خط چاپ کنید. در خط iiام جواب درخواست iiام را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3 3 2
1 1 1 1
3 3 3 3
2
1 3 3 1
1 2 1 3
Plain text

خروجی نمونه ۱🔗

4
2
Plain text

سمپل اوّل

ورودی نمونه ۲🔗

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
Plain text

خروجی نمونه ۲🔗

5
1
1
0
5
Plain text

توضیح تصویر