喺一個晴天，某個城市嘅一個十字路口發生咗綁架案。疑犯係 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$。
• 之後 $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