Одного сонячного дня на перехресті в місті сталося викрадення. Підозрюють, що злочинцями були 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