بسبب صعوبة المسائل، قرر بعض المتسابقين الهرب من هذه المسابقة. لكن واضعي المسائل الأشرار، لمنع ذلك، أنشؤوا متاهة عند مخرج الملعب. تتكون المتاهة من شبكة أبعادها $n \times m$، يقع عليها المدخل والمخرج و$k$ ثقوب سوداء. أي متسابق يطأ أحد الثقوب السوداء بالخطأ يسقط فيه، وبالتالي لن يستطيع الهرب من المسابقة أبدًا.

والأسوأ أن واضعي المسائل قد يغيرون أيضًا إحداثيات المدخل والمخرج. أنت متسابق مسكين تبدأ من المدخل وتريد الوصول إلى المخرج دون أن تطأ أي ثقب أسود، ولا يمكنك في كل خطوة سوى الانتقال إلى إحدى الخلايا الأربع المجاورة. تريد معرفة أقل عدد من الخطوات اللازمة للوصول من المدخل إلى المخرج، بعد كل مرة يغير فيها واضعو المسائل إحداثياتهما.

الإدخال

يحتوي السطر الأول من الإدخال على أربعة أعداد صحيحة $n,m,k,q$ ($1 \le n,m \le 200\,000$، $nm \le 200\,000$، $0 \le k \le 42$، $1 \le q \le 100\,000$)، تمثل على الترتيب عدد الصفوف، وعدد الأعمدة، وعدد الثقوب السوداء في المتاهة، وعدد الاستعلامات.

تصف الأسطر الـ$k$ التالية الثقوب السوداء. يحتوي كل منها على عددين صحيحين $x,y$ ($1 \le x \le n$، $1 \le y \le m$)، يمثلان إحداثيات ثقب أسود. لا يوجد ثقبان أسودان في الموضع نفسه.

تصف الأسطر الـ$q$ الأخيرة الاستعلامات. يحتوي كل منها على أربعة أعداد صحيحة $x_s,y_s,x_t,y_t$ ($1 \le x_s,x_t \le n$، $1 \le y_s,y_t \le m$)، حيث $(x_s,y_s)$ إحداثيات المدخل، و$(x_t,y_t)$ إحداثيات المخرج.

الإخراج

لكل استعلام، اطبع عددًا في سطر يمثل أقل عدد من الخطوات اللازمة للوصول من المدخل إلى المخرج. إذا كان الوصول إلى المخرج مستحيلاً، فاطبع $-1$ بدلاً من ذلك. وتُعد الحالة مستحيلة إذا كان المدخل أو المخرج يتطابق مع ثقب أسود.

أمثلة

الإدخال 1

5 5 4 7
2 2
2 3
3 2
3 3
2 1 3 4
1 1 1 1
2 2 2 2
1 1 1 5
2 2 5 5
2 1 2 4
1 1 3 3

الإخراج 1

6
0
-1
4
-1
5
-1

الإدخال 2

2 3 2 1
1 2
2 1
1 1 2 3

الإخراج 2

-1

ملاحظة

يوضح الشكل أدناه المتاهة والاستعلام الأول من بيانات المثال الأول.

(أ) المتاهة. (ب) أحد أقصر المسارات الممكنة للاستعلام الأول. مفتاح الرموز: المدخل، المخرج، الثقب الأسود، خطوة واحدة.

الشكل 1: رسومات بيانات الاختبار النموذجية.