← 返回题目列表

Codeforces · 1533/E

E. 国际象棋队组建

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

波利卡普正在指导一支队伍准备即将举行的国际象棋锦标赛比赛。参加比赛的完整队伍应由 $$$n+1$$$ 成员组成。

他的团队中有$$$n$$$名成员,第$$$i$$$个成员的技能值为$$$a_i$$$。波利卡普尚未选择团队的最终成员。

对方队伍有$$$n+1$$$名成员,第$$$j$$$个成员的技能值为$$$b_j$$$。

Polycarp 对于球队的最后一名球员有 $$$m$$$ 选项。其中第 $$$k$$$ 的技能值为 $$$c_k$$$。

比赛开始前,波利卡普将自己球队的成员与对方球队的成员配对。两队的每个成员都恰好是一对。对于某个玩家来说,游戏的难度是他配对的对手的技能与他自己的技能之间的差异。因此,如果 Polycarp 队伍的第 $$$i$$$ 玩家与对方队伍的第 $$$j$$$ 玩家配对,则难度等于 $$$b_j - a_i$$$。一支球队的比赛难度是其所有球员的最大难度。

因此,在比赛开始之前,波利卡普希望以这样的方式对球员进行配对,以使他的球队的比赛难度最小化。

对于最终玩家的每个 $$$m$$$ 选项,打印 Polycarp 团队可以实现的最小游戏难度。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — Polycarp 团队中的成员数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是 Polycarp 队伍中第 $$$i$$$ 玩家的技能值。

第三行包含$$$n+1$$$整数$$$b_1, b_2, \dots, b_{n+1}$$$ ($$$1 \le b_j \le 10^9$$$),其中$$$b_j$$$是对方队伍第$$$j$$$球员的技能值。

第四行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 最终玩家的选项数量。

第五行包含 $$$m$$$ 整数 $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_k \le 10^9$$$),其中 $$$c_k$$$ 是 Polycarp 队伍最后一名球员的第 $$$k$$$ 选项的技能值。

输出

打印 $$$m$$$ 整数 - 其中第 $$$k$$$ 个应该等于 Polycarp 选择第 $$$k$$$ 个选项玩家作为最后一名玩家时可以达到的游戏最小难度。

示例

输入 #1

5
10 3 4 6 1
9 4 2 5 9 8
5
1 7 6 4 8

输出 #1

4 2 3 4 2

输入 #2

3
5 1 8
8 2 10 1
10
1 2 3 4 5 6 7 8 9 10

输出 #2

3 3 3 3 3 2 2 2 1 0

输入 #3

1
10
10 5
2
5 15

输出 #3

0 -5

注意

在第一个示例中,前三个选项的最佳配对如下。请注意,最小答案可能有多个有效配对。

第一个选项:

波利卡普的队伍:6 1 3 1 10 4

对方球队:9 4 2 5 9 8

每个玩家的游戏难度分别为:3, 3, -1, 4, -1, 4。最大为4,因此是团队的游戏难度。

第二个选项:

波利卡普的队伍:10 4 1 3 7 6

对方球队:9 4 2 5 9 8

第三个选项:

波利卡普的队伍:6 3 1 4 10 6

对方球队:9 4 2 5 9 8