← 返回题目列表

Codeforces · 2005/B1

B1. 严厉的老师(简易版)

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

这是问题的简单版本。两个版本之间的唯一区别是 $$$m$$$ 和 $$$q$$$ 的约束。在此版本中,$$$m=2$$$ 且$$$q=1$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

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$$$, $$$m=2$$$, $$$q=1$$$) — 行上的单元格数量、教师数量和查询数量。

在每个测试用例的第二行中,您将获得 $$$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$$$。

输出

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

示例

输入 #1

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

输出 #1

1
2
2

注意

在第一个示例中,学生可以留在牢房$$$2$$$。老师最初位于单元格 $$$1$$$,一步即可到达单元格 $$$2$$$。因此,答案是$$$1$$$。

在第二个示例中,学生应该留在牢房$$$1$$$。老师最初位于单元格 $$$3$$$,可以通过两次移动到达单元格 $$$1$$$。因此,答案是$$$2$$$。