题目描述

Timur 正在一辆车上，沿着数轴从 $0$ 点行驶到 $n$ 点。汽车从 $0$ 点在第 $0$ 分钟开始出发。

数轴上有 $k+1$ 个标志牌，分别位于 $0, a_1, a_2, \dots, a_k$ 处，Timur 知道汽车分别会在第 $0, b_1, b_2, \dots, b_k$ 分钟到达这些位置。序列 $a$ 和 $b$ 都是严格递增的，且 $a_k = n$。

在任意两个相邻的标志牌之间，汽车都以恒定速度行驶。Timur 有 $q$ 个询问：每个询问给定一个整数 $d$，Timur 想让你输出汽车到达 $d$ 点所需的分钟数，向下取整。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$k$ 和 $q$（$k \leq n \leq 10^9$；$1 \leq k, q \leq 10^5$），分别表示终点位置、Timur 已知时间的点的数量和询问的数量。

每个测试用例的第二行包含 $k$ 个整数 $a_i$（$1 \leq a_i \leq n$；对于每个 $1 \leq i \leq k-1$，有 $a_i < a_{i+1}$；$a_k = n$）。

每个测试用例的第三行包含 $k$ 个整数 $b_i$（$1 \leq b_i \leq 10^9$；对于每个 $1 \leq i \leq k-1$，有 $b_i < b_{i+1}$）。

接下来的 $q$ 行，每行包含一个整数 $d$（$0 \leq d \leq n$），表示 Timur 询问的距离。

所有测试用例中 $k$ 的总和不超过 $10^5$，所有测试用例中 $q$ 的总和不超过 $10^5$。

输出格式

对于每个询问，输出一个整数，表示汽车到达 $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$ 点，时间为 $0$ 分钟。
• 在 $6$ 点，时间为 $6$ 分钟。
• 在 $7$ 点，时间为 $7$ 分钟。

对于第二个测试用例，$0$ 到 $4$ 点速度为每分钟 $1$ 单位，$4$ 到 $10$ 点速度为每分钟 $2$ 单位：

• 在 $6$ 点，时间为 $5$ 分钟。
• 在 $4$ 点，时间为 $4$ 分钟。
• 在 $2$ 点，时间为 $2$ 分钟。
• 在 $7$ 点，时间为 $5.5$ 分钟，答案为 $5$。

对于第四个测试用例，汽车速度为每分钟 $1.2$ 单位，因此各询问的答案为：

• 在 $2$ 点，时间为 $1.66\dots$ 分钟，答案为 $1$。
• 在 $6$ 点，时间为 $5$ 分钟。
• 在 $5$ 点，时间为 $4.16\dots$ 分钟，答案为 $4$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1971E，英文题名 Find the Car。