Timur 乘坐一辆车沿着数轴从点 $$$0$$$ 行驶到点 $$$n$$$。汽车在 $$$0$$$ 分钟从 $$$0$$$ 开始移动。
线路上在点 $$$0, a_1, a_2, \dots, a_k$$$ 处有 $$$k+1$$$ 标志,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$$$; $$$a_i < a_{i+1}$$$ 对于每个 $$$1 \leq i \leq k-1$$$; $$$a_k = n$$$)。
每个测试用例的第三行包含 $$$k$$$ 整数 $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$; $$$b_i < b_{i+1}$$$ 对于每个 $$$1 \leq i \leq k-1$$$)。
以下 $$$q$$$ 行中的每一行都包含一个整数 $$$d$$$ ($$$0 \leq d \leq n$$$) — Timur 询问经过的分钟数的距离。
所有测试用例的 $$$k$$$ 总和不超过 $$$10^5$$$,所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$。
输出
对于每个查询,输出一个整数 - 汽车到达点 $$$d$$$ 之前经过的分钟数,向下舍入。
示例
输入 #1
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
输出 #1
0 6 7 5 4 2 5 99999999 1 5 4
注意
对于第一个测试用例,汽车在 $$$10$$$ 分钟内从点 $$$0$$$ 行驶到 $$$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$$$。