Timur is in a car traveling on the number line from point $$$0$$$ to point $$$n$$$. The car starts moving from point $$$0$$$ at minute $$$0$$$.

There are $$$k+1$$$ signs on the line at points $$$0, a_1, a_2, \dots, a_k$$$, and Timur knows that the car will arrive there at minutes $$$0, b_1, b_2, \dots, b_k$$$, respectively. The sequences $$$a$$$ and $$$b$$$ are strictly increasing with $$$a_k = n$$$.

$\text{[math]}$

Between any two adjacent signs, the car travels with a constant speed. Timur has $$$q$$$ queries: each query will be an integer $$$d$$$, and Timur wants you to output how many minutes it takes the car to reach point $$$d$$$, rounded down to the nearest integer.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$q$$$, ($$$k \leq n \leq 10^9$$$; $$$1 \leq k, q \leq 10^5$$$) — the final destination, the number of points Timur knows the time for, and the number of queries respectively.

The second line of each test case contains $$$k$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq n$$$; $$$a_i \lt a_{i+1}$$$ for every $$$1 \leq i \leq k-1$$$; $$$a_k = n$$$).

The third line of each test case contains $$$k$$$ integers $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$; $$$b_i \lt b_{i+1}$$$ for every $$$1 \leq i \leq k-1$$$).

Each of the following $$$q$$$ lines contains a single integer $$$d$$$ ($$$0 \leq d \leq n$$$) — the distance that Timur asks the minutes passed for.

The sum of $$$k$$$ over all test cases doesn't exceed $$$10^5$$$, and the sum of $$$q$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each query, output a single integer — the number of minutes passed until the car reaches the point $$$d$$$, rounded down.

Note

For the first test case, the car goes from point $$$0$$$ to point $$$10$$$ in $$$10$$$ minutes, so the speed is $$$1$$$ unit per minute and:

At point $$$0$$$, the time will be $$$0$$$ minutes.
At point $$$6$$$, the time will be $$$6$$$ minutes.
At point $$$7$$$, the time will be $$$7$$$ minutes.

For the second test case, between points $$$0$$$ and $$$4$$$, the car travels at a speed of $$$1$$$ unit per minute and between $$$4$$$ and $$$10$$$ with a speed of $$$2$$$ units per minute and:

At point $$$6$$$, the time will be $$$5$$$ minutes.
At point $$$4$$$, the time will be $$$4$$$ minutes.
At point $$$2$$$, the time will be $$$2$$$ minutes.
At point $$$7$$$, the time will be $$$5.5$$$ minutes, so the answer is $$$5$$$.

For the fourth test case, the car travels with $$$1.2$$$ units per minute, so the answers to the queries are:

At point $$$2$$$, the time will be $$$1.66\dots$$$ minutes, so the answer is $$$1$$$.
At point $$$6$$$, the time will be $$$5$$$ minutes.
At point $$$5$$$, the time will be $$$4.16\dots$$$ minutes, so the answer is $$$4$$$.

Find the Car

Examples