Problem Statement

There are $N$ bases $1, 2, \dots, N$ arranged in a straight line. For each integer $i$ satisfying $1 \leq i \leq N - 1$, base $i$ and base $i + 1$ are connected to each other by a road, which can be traveled in time $1$.

Also, among the $N$ bases, $K_A$ of them have a type A warp zone, and $K_B$ of them have a type B warp zone.

The type A warp zones are located at bases $a_1, a_2, \dots, a_{K_A}$, and the type B warp zones are located at bases $b_1, b_2, \dots, b_{K_B}$.

If the base you are currently at has a warp zone, you can instantly move to a base that has a warp zone of the same type as that warp zone (that is, you can move in time $0$).

You are given $Q$ queries. In the $i$-th query, integers $s_i, t_i$ are given. Answer each of the queries.

• What is the minimum time required to travel from base $s_i$ to base $t_i$, using roads and warp zones any number of times each (possibly $0$ times)?

Constraints

• All inputs are integers
• $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$

Input

The input is given from standard input in the following format.

$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$

Output

Output $Q$ lines. On the $i(1 \leq i \leq Q)$-th line, output the answer to the $i$-th query.

Note that since the input and output may be large, using fast I/O methods is recommended.

Sample

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

2
0
1
0
1