В один солнечный день на городском перекрёстке произошло похищение. Подозревают, что преступниками были 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