There is a segment of length $L-1$ meters, and there are L positions on it, numbered $1,2, ... ,L$, equally spaced by 1 meter apart each, in the given order. There are n balls on it, at positions $s_1, s_2, \dots , s_n$ ($s_i < s_{i+1}$). Each ball is either rolling to the left of to the right at the speed of 1 meter/second. Whenever two balls hit each other, both of them change direction instantly but keep the same speed. A ball also changes direction when it reaches one of the ends of the segment (position 1 or L). You are given q queries, each one gives you two numbers $t_i$ and $p_i$, and you should output the position of the $p_i$-th ball after $t_i$ second.

Input

The first line contain three integers: L, n and q.

The second line contains n distinct integers $s_1, s_2, \dots , s_n$. ($s_i < s_{i+1}$)

The third line contains n integers $d_1, d_2, \dots , d_n$ ($d_i = 0$ if the i-th ball rolls to the left and $d_i = 1$ if it rolls to the right)

The following q lines each contain two numbers: $t_i$ and $p_i$.

Output

Print q lines, each containing a single integer: the i-th line should contain the answer to the i-th query. It can be proved that the answer is always an integer.

Constraints

$2 \leq L \leq 10^9$

$1 \leq n \leq min(L, 10^5)$

$1 \leq q \leq 10^5$

$1 \leq s_i \leq L$

$d_i = 0$ or $d_i = 1$

$1 \leq t_i \leq 10^9$

$1 \leq p_i \leq n$