בשל הבעיות המאתגרות, כמה מהמתחרים מחליטים לברוח מהתחרות הזאת. אולם כדי למנוע זאת, מחברי הבעיות המרושעים בנו מבוך ביציאה מהאצטדיון. המבוך בנוי מרשת בגודל $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$ השורות האחרונות מכילות את תיאור השאילתות. כל אחת מ־$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: איורים עבור נתוני הדוגמה.