問題文

$N$ 個の基地 $1, 2, \dots, N$ が，一直線上に並んでいます．$1 \leq i \leq N - 1$ を満たす整数 $i$ に対して，基地 $i$ と基地 $i + 1$ は相互に道で繋がっており，時間 $1$ で移動することができます．

また，$N$ 個の基地のうち $K_A$ 個にはタイプ A のワープゾーンが，$K_B$ 個にはタイプ B のワープゾーンがあります．

タイプ A のワープゾーンは，基地 $a_1, a_2, \dots, a_{K_A}$ に，タイプ B のワープゾーンは，基地 $b_1, b_2, \dots, b_{K_B}$ に置かれています．

今自身のいる基地にワープゾーンがあるとき，そのワープゾーンと同じ種類のワープゾーンのある基地に瞬時に移動することができます（すなわち時間 $0$ で移動できます）．

$Q$ 個のクエリが与えられます．$i$ 番目のクエリでは整数 $s_i, t_i$ が与えられるので，それぞれについて答えてください．

• 基地 $s_i$ から基地 $t_i$ まで道およびワープゾーンをそれぞれ好きな回数（$0$ 回でもよい）用いて移動するとき，かかる時間は最短でいくらか．

制約

• 入力は全て整数
• $2 \leq N \leq 3 \times 10^5$
• $2 \leq K_A, K_B \leq N$
• $1 \leq a_1 < \dots < a_{K_A} \leq N$
• $1 \leq b_1 < \dots < b_{K_B} \leq N$
• $1 \leq Q \leq 3 \times 10^5$
• $1 \leq s_i < t_i \leq N$

入力

入力は以下の形式で標準入力から与えられる．

$N$ $K_A$ $K_B$
$a_1$ $a_2$ $\dots$ $a_{K_A}$
$b_1$ $b_2$ $\dots$ $b_{K_B}$
$Q$
$s_1$ $t_1$
$s_2$ $t_2$
$\vdots$
$s_Q$ $t_Q$

出力

$Q$ 行出力せよ．$i(1 \leq i \leq Q)$ 行目には，$i$ 番目のクエリの答えを出力せよ．

なお，入出力が大きくなる場合があるため，高速な方法で入出力を行うことを推奨する．

サンプル

10 2 3
1 8
4 6 7
5
1 10
1 8
9 10
6 7
1 4

2
0
1
0
1