ביום שמש אירעה חטיפה בצומת בעיר. החשודים הם 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$ השאילתות, חשבו את מרחק הנסיעה המרבי האפשרי מהצומת המועמד הנתון.

משימה

בהינתן דרגות העומס של רחובות העיר ו-$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