Num dia ensolarado, ocorreu um sequestro num cruzamento de uma cidade. Suspeita-se de que os criminosos eram Anna e Bruno e de que fugiram do local do sequestro de carro. O carro ainda não foi encontrado. A polícia continua à sua procura.

A área urbana onde os criminosos conduziam é uma cidade em forma de grelha retangular, com $H$ ruas na direção leste-oeste e $W$ ruas na direção sul-norte. A distância entre dois cruzamentos adjacentes é de 1 quilómetro.

Cada rua tem um número inteiro, o seu grau de congestionamento. O grau de congestionamento da rua $i$ ($1 \le i \le H$), contando a partir do norte entre as ruas na direção leste-oeste, é $A_i$. O grau de congestionamento da rua $j$ ($1 \le j \le W$), contando a partir do oeste entre as ruas na direção sul-norte, é $B_j$. Estes $H+W$ valores são todos distintos. Em cada rua, o grau de congestionamento é o mesmo em todos os seus pontos.

A investigação policial revelou que os criminosos se deslocaram pela cidade da seguinte forma:

• Não saíram da cidade nem saíram das ruas.
• No início, os criminosos escolheram uma das direções possíveis a partir do local do sequestro e deslocaram-se nessa direção.
• Ao chegarem a um cruzamento, se o grau de congestionamento da rua transversal fosse maior que o da rua atual, viravam nesse cruzamento. Se fosse possível virar nas duas direções, podiam escolher qualquer uma delas.
• Ao chegarem a um cruzamento, se o grau de congestionamento da rua atual fosse maior que o da rua transversal, continuavam em frente. No entanto, se estivessem no limite da cidade e não pudessem continuar em frente, paravam nesse local.

Há $Q$ cruzamentos candidatos a local do sequestro. Estes $Q$ candidatos são todos distintos. Para determinar o número de investigadores, a polícia quer saber, para cada cruzamento candidato, a maior distância que os criminosos poderiam ter percorrido, supondo que o sequestro ocorreu nesse local.

Para cada uma das $Q$ consultas, calcule a maior distância possível percorrida a partir do cruzamento candidato indicado.

Tarefa

Dados os graus de congestionamento das ruas da cidade e $Q$ cruzamentos candidatos a local do sequestro, escreva um programa que calcule a maior distância possível percorrida a partir de cada cruzamento candidato.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém três inteiros $H,W,Q$ separados por espaços. Isto significa que a cidade é uma grelha retangular com $H$ ruas na direção leste-oeste e $W$ ruas na direção sul-norte, e que há $Q$ cruzamentos candidatos a local do sequestro.
• A segunda linha contém $H$ inteiros $A_1,A_2,\ldots,A_H$ separados por espaços. Isto significa que o grau de congestionamento da rua $i$ ($1 \le i \le H$), contando a partir do norte entre as ruas na direção leste-oeste, é $A_i$.
• A terceira linha contém $W$ inteiros $B_1,B_2,\ldots,B_W$ separados por espaços. Isto significa que o grau de congestionamento da rua $j$ ($1 \le j \le W$), contando a partir do oeste entre as ruas na direção sul-norte, é $B_j$.
• A linha $k$ ($1 \le k \le Q$) das $Q$ linhas seguintes contém dois inteiros $S_k,T_k$ separados por espaços. Isto significa que o cruzamento candidato $k$ a local do sequestro é o cruzamento da rua $S_k$, contando a partir do norte entre as ruas na direção leste-oeste, com a rua $T_k$, contando a partir do oeste entre as ruas na direção sul-norte.

Saída

Escreva $Q$ linhas na saída padrão. A linha $k$ deve conter um inteiro: a maior distância possível percorrida (em quilómetros) a partir do cruzamento candidato $k$ a local do sequestro.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $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$).
• Os $H+W$ inteiros $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ são todos distintos.
• $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$).

Subtarefas

Há 5 subtarefas. As pontuações e restrições adicionais de cada subtarefa são as seguintes:

Subtarefa 1 [13 pontos]

• $H \le 8$.
• $W \le 8$.
• $Q=1$.

Subtarefa 2 [10 pontos]

• $H \le 2\,000$.
• $W \le 2\,000$.
• $Q=1$.

Subtarefa 3 [17 pontos]

• $Q=1$.

Subtarefa 4 [4 pontos]

• $H \le 2\,000$.
• $W \le 2\,000$.

Subtarefa 5 [56 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

3 3 5
3 2 6
1 4 5
1 1
1 2
2 2
3 1
3 3

Saída 1

4
5
4
4
2

Nota

Por exemplo, para a terceira consulta, a distância percorrida atinge o valor máximo se os criminosos se deslocarem da seguinte forma:

• Deslocam-se 1 quilómetro para leste a partir do cruzamento da segunda rua a contar do norte com a segunda rua a contar do oeste.
• A partir do cruzamento da segunda rua a contar do norte com a terceira rua a contar do oeste, podem deslocar-se para sul ou para norte. Escolhem deslocar-se 1 quilómetro para sul.
• A partir do cruzamento da terceira rua a contar do norte com a terceira rua a contar do oeste, só podem deslocar-se para oeste. Deslocam-se 1 quilómetro para oeste.
• A partir do cruzamento da terceira rua a contar do norte com a segunda rua a contar do oeste, só podem deslocar-se para oeste. Deslocam-se 1 quilómetro para oeste.
• Não podem deslocar-se a partir do cruzamento da terceira rua a contar do norte com a primeira rua a contar do oeste. Param nesse local.

Se se deslocarem como descrito acima, a distância percorrida é de 4 quilómetros.

Entrada 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

Saída 2

7
6
9
4
6
9