1971E · Find the Car

Problem: 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$.

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 Format: 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 < 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 < 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 Format: 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$.