AT_joi2020ho_a.長いだけのネクタイ (Just Long Neckties)

你知道 Just Odd Inventions 公司吗？这家公司的业务就是“只做奇怪的发明（just odd inventions）”。在这里简称为 JOI 公司。

JOI 公司开发了一款新产品“只是很长的领带”。领带共有 $N+1$ 种，每种领带编号为 $1$ 到 $N+1$。第 $i$ 种领带的长度为 $A_i$。

JOI 公司召集了员工，举行了一场领带试穿会。试穿会有 $N$ 名员工参加，第 $j$ 名员工最初佩戴的领带长度为 $B_j$。

试穿会按以下步骤进行：

1. 首先，从所有领带中选择一种不参与试穿会。
2. 接着，每位员工从剩下的领带中选择一种进行试穿。注意，任何两位员工不能选择同一种领带。
3. 最后，每位员工摘下自己原本佩戴的领带，试穿刚才选中的领带。

一名原本佩戴长度为 $b$ 的领带的员工，试穿长度为 $a$ 的领带时，会感受到大小为 $\max\{a-b, 0\}$ 的“奇妙感”。（这里，$\max\{a-b, 0\}$ 表示 $a-b$ 和 $0$ 中较大的那个数。）试穿会中所有员工感受到的“奇妙感”的最大值，称为这场试穿会的奇妙度。

当第 $k$ 种领带不参与试穿会时，试穿会可能达到的最小奇妙度记为 $C_k$。

给定每种领带的长度和每位员工最初佩戴的领带长度，请编写程序求出 $C_1, C_2, \ldots, C_{N+1}$ 的值。

输入以如下格式从标准输入读入。所有输入均为整数。

$N$ $A_1$ $\cdots$ $A_{N+1}$ $B_1$ $\cdots$ $B_N$

请将 $C_1, C_2, \ldots, C_{N+1}$ 的值以空格分隔，输出在一行中。

约束条件

• $1 \leq N \leq 200\,000$。
• $1 \leq A_i \leq 1\,000\,000\,000$（$1 \leq i \leq N+1$）。
• $1 \leq B_j \leq 1\,000\,000\,000$（$1 \leq j \leq N$）。

子任务

1.（1 分）$N \leq 10$。
2.（8 分）$N \leq 2\,000$。
3.（91 分）无额外约束。

---

样例解释 1

例如，试穿会可以这样进行：

• 不使用第 4 种领带。
• 员工 1 选择第 1 种，员工 2 选择第 2 种，员工 3 选择第 3 种领带。
• 每位员工试穿领带。

此时，每位员工感受到的奇妙感依次为 $2, 0, 3$，因此这场试穿会的奇妙度为 $3$。通过改变员工选择的领带，可以将奇妙度降为 $1$。例如，试穿会可以这样进行：

• 不使用第 4 种领带。
• 员工 1 选择第 2 种，员工 2 选择第 3 种，员工 3 选择第 1 种领带。
• 每位员工试穿领带。

此时，每位员工感受到的奇妙感依次为 $1, 1, 0$，因此这场试穿会的奇妙度为 $1$。这就是不使用第 4 种领带时试穿会奇妙度的最小值，所以 $C_4 = 1$。

由 ChatGPT 4.1 翻译