เนื่องจากโจทย์ที่ท้าทาย ผู้เข้าแข่งขันบางคนจึงตัดสินใจหนีออกจากการแข่งขันครั้งนี้ อย่างไรก็ตาม เพื่อป้องกันไม่ให้เกิดเรื่องนี้ขึ้น ผู้แต่งโจทย์ผู้ชั่วร้ายได้สร้างเขาวงกตไว้ตรงทางออกของสนามกีฬา เขาวงกตเป็นตารางขนาด $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

หมายเหตุ

ภาพของเขาวงกตและคำถามแรกของข้อมูลตัวอย่างชุดแรกแสดงอยู่ด้านล่าง

(a) เขาวงกต (b) เส้นทางสั้นที่สุดที่เป็นไปได้เส้นทางหนึ่งสำหรับคำถามแรก

คำอธิบายสัญลักษณ์: ทางเข้า ทางออก หลุมดำ หนึ่งก้าว

รูปที่ 1: ภาพประกอบข้อมูลทดสอบตัวอย่าง