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

---

ربات‌های KMJ نسل جدید ربات های اسکیت روی یخ هستند. برای آزمایش این ربات‌ها، یک زمین اسکیت روی یخ که به صورت یک مستطیل شبکه‌بندی شده است طراحی شده و تعدادی مانع در آن قرار داده شده است. در واقع، زمین اسکیت را می‌توان به صورت مستطیلی با $n$ سطر و $m$ ستون درنظرگرفت که در برخی از خانه‌های آن مانع قرار دارد. برای اسکیت کردن ربات‌ها، چهار فرمان بالا، چپ، پایین و راست درنظرگرفته شده است. هنگامی که یک ربات جهتی را می‌شنود، در آن جهت حرکت می‌کند تا به یک مانع برخورد کند و یا این که به مرزهای زمین اسکیت برسد.

شما باید برنامه‌ای بنویسید که به $q$ پرسش به فرم $r_1 c_1 r_2 c_2$ پاسخ دهد. هر پرسش به این معنا است که اگر در ابتدا یک ربات در خانه‌ی $(r_1,c_1)$ و یک ربات دیگر در خانه‌ی $(r_2,c_2)$ باشد، کمترین طول دنباله‌ای از دستورها که این دو ربات بعد از اجرای آن در یک خانه قرار داشته باشند، چقدر است. در صورتی که چنین دنباله‌ای از دستورها وجود نداشته باشد، برنامه‌‌ی شما باید عدد $1-$ را به عنوان جواب در نظر بگیرد.

ورودی

سطر اول ورودی شامل سه عدد طبیعی $n$، تعداد سطرها، $m$، تعداد ستون‌ها و $k$، تعداد مانع‌ها است.

سپس در هر کدام از سطرهای $2$ تا $k+1$ ، دو عدد طبیعی $r_i$ و $c_i$ آمده است که به ترتیب شماره‌ی سطر و شماره‌ی ستون مانع $i$ام را نشان می‌دهند.

در سطر $k+2$ ام ، عدد طبیعی $q$ تعداد پرسمان‌ها می‌آید.

در هریک از $q$ سطر بعدی به ترتیب چهار عدد طبیعی $r_1 c_1 r_2 c_2$ می آید که نشان دهنده‌ی یک پرسمان هستند. تضمین می‌شود مانع‌ها در خانه‌های متمایز هستند و ربات‌هایی که در پرسمان‌ها می‌آیند، در خانه‌های غیر مانع هستند. $$ 1 \leq n,m,k \leq 400$$

$$ 1 \leq q \leq 100\ 000 $$

خروجی

خروجی شامل $q$ سطر است که در سطر $i$ام پاسخ پرسش شماره $i$ آمده است.

زیرمسئله‌ها

زیرمسئله	شماره‌ی تست‌ها	نمره	محدودیت
۱	۱ تا ۱۰	۱۰۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 4 3
1 2
2 4
3 1
3
2 3 2 2
2 2 4 4
4 4 2 1

خروجی نمونه ۱

1
2
3

ورودی نمونه ۲

2 2 2
1 2
2 1
2
1 1 1 1
1 1 2 2

خروجی نمونه ۲

0
-1

۲۵امین دوره المپیاد کامپیوتر - آزمون اول- ۱۳۹۴/۵/۳۱