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\)