311340: CF1971E. Find the Car

E. Find the Cartime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5

Output

0 6 7 
5 4 2 5 
99999999 
1 5 4 

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

题目大意：
Timur在一辆车上，沿着数轴从点0到点n行驶。汽车从点0开始于第0分钟启动。在线上有k+1个标志，分别位于0, a_1, a_2, ..., a_k点，Timur知道汽车将在分别在第0, b_1, b_2, ..., b_k分钟到达那里。序列a和b是严格递增的，其中a_k = n。在任何两个相邻标志之间，汽车以恒定速度行驶。Timur有q个查询：每个查询将是一个整数d，Timur希望您输出汽车到达点d所需的时间，向下取整到最近的整数。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。
- 每个测试用例的第一行包含三个整数n, k, q（k ≤ n ≤ 10^9; 1 ≤ k, q ≤ 10^5）——最终目的地、Timur知道的时间点的数量和查询的数量。
- 每个测试用例的第二行包含k个整数a_i（1 ≤ a_i ≤ n; a_i < a_{i+1}对于每个1 ≤ i ≤ k-1; a_k = n）。
- 每个测试用例的第三行包含k个整数b_i（1 ≤ b_i ≤ 10^9; b_i < b_{i+1}对于每个1 ≤ i ≤ k-1）。
- 接下来的q行，每行包含一个整数d（0 ≤ d ≤ n）——Timur询问汽车到达该点所需的时间。

输出：
- 对于每个查询，输出一个整数——汽车到达点d所需的时间，向下取整。

示例：
输入：
```
4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5
```
输出：
```
0 6 7
5 4 2 5
99999999
1 5 4
```

注意：
- 对于第一个测试用例，汽车从点0到点10需要10分钟，因此速度是每分钟1单位。
- 对于第二个测试用例，汽车在点0和点4之间以每分钟1单位的速度行驶，在点4和点10之间以每分钟2单位的速度行驶。
- 对于第四个测试用例，汽车以每分钟1.2单位的速度行驶。题目大意： Timur在一辆车上，沿着数轴从点0到点n行驶。汽车从点0开始于第0分钟启动。在线上有k+1个标志，分别位于0, a_1, a_2, ..., a_k点，Timur知道汽车将在分别在第0, b_1, b_2, ..., b_k分钟到达那里。序列a和b是严格递增的，其中a_k = n。在任何两个相邻标志之间，汽车以恒定速度行驶。Timur有q个查询：每个查询将是一个整数d，Timur希望您输出汽车到达点d所需的时间，向下取整到最近的整数。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。 - 每个测试用例的第一行包含三个整数n, k, q（k ≤ n ≤ 10^9; 1 ≤ k, q ≤ 10^5）——最终目的地、Timur知道的时间点的数量和查询的数量。 - 每个测试用例的第二行包含k个整数a_i（1 ≤ a_i ≤ n; a_i < a_{i+1}对于每个1 ≤ i ≤ k-1; a_k = n）。 - 每个测试用例的第三行包含k个整数b_i（1 ≤ b_i ≤ 10^9; b_i < b_{i+1}对于每个1 ≤ i ≤ k-1）。 - 接下来的q行，每行包含一个整数d（0 ≤ d ≤ n）——Timur询问汽车到达该点所需的时间。 输出： - 对于每个查询，输出一个整数——汽车到达点d所需的时间，向下取整。 示例： 输入： ``` 4 10 1 3 10 10 0 6 7 10 2 4 4 10 4 7 6 4 2 7 1000000000 1 1 1000000000 1000000000 99999999 6 1 3 6 5 2 6 5 ``` 输出： ``` 0 6 7 5 4 2 5 99999999 1 5 4 ``` 注意： - 对于第一个测试用例，汽车从点0到点10需要10分钟，因此速度是每分钟1单位。 - 对于第二个测试用例，汽车在点0和点4之间以每分钟1单位的速度行驶，在点4和点10之间以每分钟2单位的速度行驶。 - 对于第四个测试用例，汽车以每分钟1.2单位的速度行驶。