题目描述

译自 JOI 2020 Final T1「長いだけのネクタイ / Just Long Neckties」

你知道 Just Odd Inventions 公司吗？这个公司的业务是「只不过是奇妙的发明 / Just Odd Inventions」。这里简称为 JOI 公司。

JOI 公司的最新发明是「只不过是长的领带」。共有 $N+1$ 条领带，并以 $1,\ldots,N+1$ 编号。
第 $i$ 种领带的长度为 $A_i$，其中 $1 \le i \le N+1$。

公司聚集了他们的员工，并准备举办一场试戴派对。
参加该聚会的员工共有 $N$ 个，且第 $j$ 个员工一开始戴着长度为 $B_j$ 的领带，其中 $1 \le j \le N$。
派对的流程如下：

1. JOI 公司的 CEO 首先选出一条领带，它将不会在接下来的派对中使用。
2. 然后，每个员工从其余领带中选择一条，且需保证没有两个员工选择了同一条领带。
3. 最终，每个员工取下一开始戴着的领带，并试戴他 / 她选择的领带。

若某个员工一开始戴着的领带长度为 $b$ 而最后试戴的领带长度为 $a$，则他 / 她会产生 $\max\{a - b,0\}$ 个单位的奇怪感。
整场派对的奇怪度定义为所有员工中最大的奇怪感。

由此，我们定义 $C_k$ 为当 CEO 选择第 $k$ 条领带时，整场派对最后可能的最小奇怪度。

请你对于给定的 $A_1,A_2,\ldots,A_{N+1}$ 和 $B_1,B_2,\ldots,B_N$ 求出 $C_1,C_2,\ldots,C_{N+1}$。

输入格式

第一行，一个正整数 $N$，表示员工总数。
第二行，$N+1$ 个正整数 $A_1,A_2,\ldots,A_{N+1}$，表示每条领带的长度。
第三行，$N$ 个正整数，$B_1,B_2,\ldots,B_N$，表示每个员工初始穿戴的领带的长度。

输出格式

一行，$N+1$ 个整数 $C_1,C_2,\ldots,C_{N+1}$。

样例 1

3
4 3 7 6
2 6 4

2 2 1 1

以下为一场试戴派对的例子：

• CEO 选择第 $4$ 条领带。
• 员工 $1$ 选择第 $1$ 条领带，员工 $2$ 选择第 $2$ 条领带，员工 $3$ 选择第 $3$ 条领带。
• 每个员工试戴其选择的领带。

此时，所有员工的奇怪感分别为 $2, 0, 3$，故整场派对的奇怪度为 $3$。

实际上，我们可以通过改变员工的决策将整场派对的奇怪度减少到 $1$。例如：

• CEO 选择第 $4$ 条领带。
• 员工 $1$ 选择第 $2$ 条领带，员工 $2$ 选择第 $3$ 条领带，员工 $3$ 选择第 $1$ 条领带。
• 每个员工试戴其选择的领带。

此时，所有员工的奇怪感分别为 $1, 1, 0$，故整场派对的奇怪度为 $1$。 若 CEO 选择第 $4$ 条领带，这便是可能的最小的奇怪度，因此 $C_4 = 1$。

5
4 7 9 10 11 12
3 5 7 9 11

4 4 3 2 2 2

数据范围与提示

对于所有测试数据，$1 \le N \le 2 \times 10^5, 1 \le A_i \le 10^9, 1 \le B_j \le 10^9\ (1 \le i \le N+1, 1 \le j \le N)$。