← 返回题目列表

Codeforces · 2005/B2

B2. 严厉的老师(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。两个版本之间的唯一区别是 $$$m$$$ 和 $$$q$$$ 的约束。在此版本中,$$$m, q \le 10^5$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

Narek和Tsovak正忙着准备这一轮,所以他们没有完成作业,决定偷走David的作业。他们严厉的老师注意到大卫没有作业,现在想惩罚他。她聘请了其他老师来帮助她抓住大卫。现在$$$m$$$老师一起追他。幸运的是,教室很大,大卫有很多地方可以躲。

教室可以表示为一条一维线,其单元格从 $$$1$$$ 到 $$$n$$$(含)。

一开始,所有 $$$m$$$ 老师和 David 都在不同的牢房中。然后他们采取行动。每次移动过程中

- David 前往相邻的牢房或留在当前牢房。
- 然后,每位 $$$m$$$ 教师同时前往相邻牢房或停留在当前牢房。

这一直持续到大卫被抓住。如果任何老师(可能不止一名)与大卫位于同一牢房,大卫就会被抓住。每个人都看到别人的举动,所以他们都会采取最佳行动。

你的任务是找出如果老师们都表现最佳,需要多少步才能抓住大卫。

最佳行动意味着学生以最大化老师抓住他所需的动作数量的方式做出动作;老师们互相协调,以尽量减少抓住学生所需的动作数量。

另外,由于 Narek 和 Tsovak 认为这项任务很容易,他们决定向您提供有关 David 位置的 $$$q$$$ 查询。

输入

在输入的第一行中,您将获得一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。每个测试用例的描述如下。

在每个测试用例的第一行,您将获得三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$3 \le n \le 10^9$$$, $$$1 \le m, q \le 10^5$$$) — 行上的单元格数量、教师数量和查询数量。

在每个测试用例的第二行中,您将获得 $$$m$$$ 不同的整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le n$$$) — 教师的单元格编号。

在每个测试用例的第三行中,您将获得 $$$q$$$ 整数 $$$a_1, a_2, \ldots, a_q$$$ ($$$1 \le a_i \le n$$$) - 每个查询的 David 的单元格编号。

保证对于任何 $$$i$$$, $$$j$$$ 满足 $$$1 \le i \le m$$$ 和 $$$1 \le j \le q$$$, $$$b_i \neq a_j$$$。

保证所有测试用例的 $$$m$$$ 值之和不超过 $$$2 \cdot 10^5$$$。

保证所有测试用例的 $$$q$$$ 值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 行,其中第 $$$i$$$ 包含第 $$$i$$$ 查询的答案。

示例

输入 #1

2
8 1 1
6
3
10 3 3
1 4 8
2 3 10

输出 #1

5
1
1
2

注意

在第一个示例的唯一查询中,学生可以运行到单元格 $$$1$$$。教师需要移动 5 步才能从单元格 $$$6$$$ 到达单元格 $$$1$$$,所以答案是 $$$5$$$。

在第二个示例的第二个查询中,学生可以仅停留在单元格 $$$3$$$ 中。老师最初位于单元格 $$$4$$$,一步即可到达单元格 $$$3$$$。因此,答案是$$$1$$$。