في يوم مشمس، وقعت حادثة اختطاف عند تقاطع في مدينة. يُشتبه في أن المجرمين هما Anna وBruno، وأنهما هربا من موقع الاختطاف بسيارة. لم يُعثر على السيارة بعد، ولا تزال الشرطة تبحث عنها.

المنطقة الحضرية التي قاد فيها المجرمان السيارة عبارة عن شبكة مستطيلة، فيها $H$ شوارع تمتد من الشرق إلى الغرب و$W$ شوارع تمتد من الجنوب إلى الشمال. المسافة بين كل تقاطعين متجاورين هي كيلومتر واحد.

لكل شارع عدد صحيح يسمى درجة الازدحام. درجة ازدحام الشارع ذي الترتيب $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$).
• الأعداد الصحيحة $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$، البالغ عددها $H+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

ملاحظة

على سبيل المثال، في الاستعلام الثالث، تتحقق أكبر مسافة إذا تحرك المجرمان كما يلي:

• تحركا شرقًا لمسافة كيلومتر واحد من تقاطع الشارع الثاني من الشمال والشارع الثاني من الغرب.
• من تقاطع الشارع الثاني من الشمال والشارع الثالث من الغرب، كان بإمكانهما التحرك جنوبًا أو شمالًا. اختارا التحرك جنوبًا لمسافة كيلومتر واحد.
• من تقاطع الشارع الثالث من الشمال والشارع الثالث من الغرب، لم يكن بإمكانهما التحرك إلا غربًا. فتحركا غربًا لمسافة كيلومتر واحد.
• من تقاطع الشارع الثالث من الشمال والشارع الثاني من الغرب، لم يكن بإمكانهما التحرك إلا غربًا. فتحركا غربًا لمسافة كيلومتر واحد.
• لم يتمكنا من التحرك من تقاطع الشارع الثالث من الشمال والشارع الأول من الغرب، فتوقفا عن الحركة في ذلك المكان.

إذا تحركا كما سبق، تكون المسافة المقطوعة $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