ในวันที่อากาศแจ่มใสวันหนึ่ง เกิดเหตุลักพาตัวที่ทางแยกแห่งหนึ่งในเมือง ผู้ต้องสงสัยคือ Anna และ Bruno ซึ่งหลบหนีจากที่เกิดเหตุด้วยรถยนต์ ยังไม่พบรถคันนั้น และตำรวจก็ยังคงตามหาอยู่

บริเวณเมืองที่คนร้ายขับรถผ่านเป็นตารางสี่เหลี่ยมผืนผ้า มีถนนแนวตะวันออก–ตะวันตก $H$ สาย และถนนแนวใต้–เหนือ $W$ สาย ระยะห่างระหว่างทางแยกที่อยู่ติดกันคือ 1 กิโลเมตร

ถนนแต่ละสายมีค่าจำนวนเต็มที่เรียกว่า ระดับความแออัด ถนนแนวตะวันออก–ตะวันตกสายที่ $i$ เมื่อนับจากทิศเหนือ ($1\le i\le H$) มีระดับความแออัด $A_i$ และถนนแนวใต้–เหนือสายที่ $j$ เมื่อนับจากทิศตะวันตก ($1\le j\le W$) มีระดับความแออัด $B_j$ ค่าทั้ง $H+W$ ค่านี้แตกต่างกันทั้งหมด สำหรับถนนแต่ละสาย ระดับความแออัดมีค่าเท่ากันทุกจุดบนถนนสายนั้น

การสืบสวนของตำรวจพบว่าคนร้ายเดินทางในเมืองตามกฎต่อไปนี้:

• พวกเขาไม่ออกนอกเมืองและไม่ออกนอกถนน
• ในตอนเริ่มต้น พวกเขาเลือกทิศทางหนึ่งที่สามารถเดินทางได้จากจุดเกิดเหตุ แล้วเคลื่อนที่ไปในทิศทางนั้น
• เมื่อมาถึงทางแยก หากถนนที่ตัดผ่านมีระดับความแออัดสูงกว่าถนนปัจจุบัน พวกเขาจะเลี้ยวที่ทางแยกนั้น หากเลี้ยวได้ทั้งสองทิศทาง ก็สามารถเลือกทิศทางใดก็ได้
• เมื่อมาถึงทางแยก หากถนนปัจจุบันมีระดับความแออัดสูงกว่าถนนที่ตัดผ่าน พวกเขาจะตรงต่อไป แต่หากอยู่ที่ขอบเมืองและไม่สามารถตรงต่อไปได้ พวกเขาจะหยุดที่จุดนั้น

มีทางแยกที่อาจเป็นจุดเกิดเหตุอยู่ $Q$ แห่ง ซึ่งแตกต่างกันทั้งหมด เพื่อกำหนดจำนวนเจ้าหน้าที่สืบสวน ตำรวจต้องการทราบระยะทางมากที่สุดที่คนร้ายอาจเดินทางได้จากทางแยกแต่ละแห่ง โดยสมมติว่าเหตุลักพาตัวเกิดขึ้นที่นั่น

สำหรับคำถามแต่ละข้อจากทั้งหมด $Q$ ข้อ ให้คำนวณระยะทางมากที่สุดที่อาจเดินทางได้จากทางแยกที่กำหนด

งาน

เมื่อกำหนดระดับความแออัดของถนนในเมืองและทางแยก $Q$ แห่งที่อาจเป็นจุดเกิดเหตุ ให้เขียนโปรแกรมคำนวณระยะทางมากที่สุดที่อาจเดินทางได้จากทางแยกแต่ละแห่ง

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากอินพุตมาตรฐาน

• บรรทัดแรกมีจำนวนเต็มสามจำนวน $H,W,Q$ คั่นด้วยช่องว่าง หมายความว่าเมืองเป็นตารางสี่เหลี่ยมผืนผ้าที่มีถนนแนวตะวันออก–ตะวันตก $H$ สาย และถนนแนวใต้–เหนือ $W$ สาย และมีทางแยกที่อาจเป็นจุดเกิดเหตุ $Q$ แห่ง
• บรรทัดที่สองมีจำนวนเต็ม $H$ จำนวน $A_1,A_2,\ldots,A_H$ คั่นด้วยช่องว่าง หมายความว่าถนนแนวตะวันออก–ตะวันตกสายที่ $i$ เมื่อนับจากทิศเหนือ ($1\le i\le H$) มีระดับความแออัด $A_i$
• บรรทัดที่สามมีจำนวนเต็ม $W$ จำนวน $B_1,B_2,\ldots,B_W$ คั่นด้วยช่องว่าง หมายความว่าถนนแนวใต้–เหนือสายที่ $j$ เมื่อนับจากทิศตะวันตก ($1\le j\le W$) มีระดับความแออัด $B_j$
• บรรทัดที่ $k$ ($1\le k\le Q$) จาก $Q$ บรรทัดถัดมามีจำนวนเต็มสองจำนวน $S_k,T_k$ คั่นด้วยช่องว่าง หมายความว่าทางแยกที่อาจเป็นจุดเกิดเหตุแห่งที่ $k$ คือจุดตัดของถนนแนวตะวันออก–ตะวันตกสายที่ $S_k$ เมื่อนับจากทิศเหนือ กับถนนแนวใต้–เหนือสายที่ $T_k$ เมื่อนับจากทิศตะวันตก

ข้อมูลส่งออก

เขียน $Q$ บรรทัดไปยังเอาต์พุตมาตรฐาน บรรทัดที่ $k$ ต้องมีจำนวนเต็มหนึ่งจำนวน คือระยะทางมากที่สุดที่อาจเดินทางได้จากทางแยกที่อาจเป็นจุดเกิดเหตุแห่งที่ $k$ โดยมีหน่วยเป็นกิโลเมตร

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $2\le H\le 50\,000$
• $2\le W\le 50\,000$
• $1\le Q\le 100$
• $1\le A_i\le 1\,000\,000\,000$ ($1\le i\le H$)
• $1\le B_j\le 1\,000\,000\,000$ ($1\le j\le W$)
• จำนวนเต็ม $H+W$ จำนวน $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ แตกต่างกันทั้งหมด
• $1\le S_k\le H$ ($1\le k\le Q$)
• $1\le T_k\le W$ ($1\le k\le Q$)
• $(S_k,T_k)\ne(S_l,T_l)$ ($1\le k<l\le Q$)

งานย่อย

มี 5 งานย่อย โดยคะแนนและข้อจำกัดเพิ่มเติมของแต่ละงานย่อยมีดังนี้

งานย่อย 1 [13 คะแนน]

• $H\le 8$
• $W\le 8$
• $Q=1$

งานย่อย 2 [10 คะแนน]

• $H\le 2\,000$
• $W\le 2\,000$
• $Q=1$

งานย่อย 3 [17 คะแนน]

• $Q=1$

งานย่อย 4 [4 คะแนน]

• $H\le 2\,000$
• $W\le 2\,000$

งานย่อย 5 [56 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

3 3 5
3 2 6
1 4 5
1 1
1 2
2 2
3 1
3 3

ข้อมูลส่งออก 1

4
5
4
4
2

หมายเหตุ

ตัวอย่างเช่น สำหรับคำถามที่สาม ระยะทางจะมีค่ามากที่สุดหากคนร้ายเดินทางดังนี้:

• เคลื่อนที่ไปทางตะวันออก 1 กิโลเมตรจากจุดตัดของถนนสายที่สองนับจากทิศเหนือกับถนนสายที่สองนับจากทิศตะวันตก
• ที่จุดตัดของถนนสายที่สองนับจากทิศเหนือกับถนนสายที่สามนับจากทิศตะวันตก พวกเขาสามารถไปทางใต้หรือทางเหนือก็ได้ พวกเขาเลือกไปทางใต้ 1 กิโลเมตร
• ที่จุดตัดของถนนสายที่สามนับจากทิศเหนือกับถนนสายที่สามนับจากทิศตะวันตก พวกเขาไปได้เฉพาะทางตะวันตก จึงไปทางตะวันตก 1 กิโลเมตร
• ที่จุดตัดของถนนสายที่สามนับจากทิศเหนือกับถนนสายที่สองนับจากทิศตะวันตก พวกเขาไปได้เฉพาะทางตะวันตก จึงไปทางตะวันตก 1 กิโลเมตร
• ที่จุดตัดของถนนสายที่สามนับจากทิศเหนือกับถนนสายแรกนับจากทิศตะวันตก พวกเขาไม่สามารถเคลื่อนที่ต่อได้ จึงหยุดที่จุดนั้น

หากเดินทางตามข้างต้น ระยะทางจะเท่ากับ 4 กิโลเมตร

ข้อมูลนำเข้า 2

4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3

ข้อมูลส่งออก 2

7
6
9
4
6
9