在一個晴朗的日子，某座城市的一個路口發生了綁架事件。嫌犯據信是 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$。
• 接下來 $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