实验样本（sample）

题目描述

Y 同学近期正在进行一项精密物理实验，手中共有 $N+1$ 个实验样本，编号为 $1 \sim N+1$。第 $i$ 个样本的纯度为 $A_i$。

实验室内备有 $N$ 台检测仪器，第 $j$ 台仪器对样本的基准纯度需求为 $B_j$。为了完成实验，Y 同学需要执行以下步骤：

1. 从 $N+1$ 个样本中选出某一个样本并将其移除。
2. 将剩余的 $N$ 个样本与 $N$ 台检测仪器进行一一对应（即每个样本进入一台不同的仪器）。
3. 对于每一对匹配的样本（纯度为 $a$）与仪器（基准纯度为 $b$），会产生大小为 $\max\{a - b, 0\}$ 的实验误差。

整场实验的“系统不稳定度”定义为所有 $N$ 对匹配中产生的实验误差的最大值。

设 $C_k$ 为 Y 同学移除第 $k$ 个样本后，通过最优匹配方案所能达到的最小系统不稳定度。请你帮助 Y 同学求出所有的 $C_k$（$1 \le k \le N+1$）。

输入格式

第一行包含一个整数 $N$，表示仪器的数量。 第二行包含 $N+1$ 个整数 $A_1, A_2, \dots, A_{N+1}$，表示每个实验样本的纯度。 第三行包含 $N$ 个整数 $B_1, B_2, \dots, B_N$，表示每台仪器的基准纯度需求。

输出格式

输出一行 $N+1$ 个整数，依次为 $C_1, C_2, \dots, C_{N+1}$，相邻两个数之间用空格隔开。

样例

样例输入 #1

3
4 3 7 6
2 6 4

样例输出 #1

2 2 1 1

样例输入 #2

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

样例输出 #2

4 4 3 2 2 2

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 2 \times 10^5$，$1 \le A_i, B_j \le 10^9$。

测试点编号	分值	$N \le$	特殊性质
$1 \sim 4$	20	$10$	无
$5 \sim 8$		$2000$
$9 \sim 12$		$2 \times 10^5$	特殊性质 A
$13 \sim 16$			特殊性质 B
$17 \sim 20$			无

• 特殊性质 A：保证输入的序列均已按升序排列，即 $A_i \le A_{i+1}$ 且 $B_j \le B_{j+1}$。
• 特殊性质 B：保证所有的 $B_j$ 均相等。