#3252. 「JOI 2020 Final」只不过是长的领带

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: alpha1022

题目描述

译自 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

样例输出 1

2 2 1 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

样例输入 2

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

样例输出 2

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)

子任务编号 分值 N
1 1 N \le 10
2 8 N \le 2000
3 91