Ашық күндердің бірінде қаладағы бір жол қиылысында адам ұрлау оқиғасы орын алды. Қылмыскерлер Анна мен Бруно деп күдіктеледі, және олар ұрлау орнынан автокөлікпен қашып кеткен. Автокөлік әлі табылған жоқ. Полиция оны қазір де іздестіріп жатыр.

Қылмыскерлер автокөлікпен жүрген қала аумағы шығыс-батыс бағытында созылған $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$ екенін білдіреді.
• Келесі $Q$ жолдың $k$-шы жолында ($1 \le k \le 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