题目描述

JOI 公司发明了一种领带，一共有 $N+1$ 条领带，编号为 $1$ 到 $N+1$，第 $i$ 条领带的长度为 $A_i$。

JOI 公司开了一个派对，派对中有 $N$ 名员工，第 $j$ 名员工刚开始戴了长度为 $B_j$ 的领带。

派对这样举行：

1. 首先，JOI 公司的老板 JOI 君选出一条领带拿走。
2. 然后，每个员工选一条领带，保证没有两名员工选了相同的领带。
3. 最后，他们取下最先戴的领带，戴上选择的领带。

如果一名员工刚开始戴的领带长度为 $b$，选择的领带长度为 $a$，那么他就会产生 $\max\{a-b,0\}$ 的奇怪感，整场派对的奇怪程度为所有员工的奇怪感的最大值。

于是 JOI 君定义 $C_k$ 为他选出第 $k$ 条领带后的最小奇怪程度。

JOI 君想知道 $C_k$ 的具体值。

输入格式

第一行一个整数 $N$ 代表员工数。
第二行 $N+1$ 个整数 $A_i$ 代表每个领带的长度。
第三行 $N$ 个整数 $B_j$ 代表每个人最开始戴的领带的长度。

输出格式

一行 $N+1$ 个整数 $C_k$ 代表选出每个领带后的最小奇怪程度。

3
4 3 7 6
2 6 4

2 2 1 1

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

4 4 3 2 2 2

提示

样例 1 解释

让我们假设 JOI 君选择了第 $4$ 条领带，那么员工们可以这么选择：

• 第 $1$ 名员工选择第 $1$ 条领带，产生奇怪感 $2$
• 第 $2$ 名员工选择第 $2$ 条领带，产生奇怪感 $0$
• 第 $3$ 名员工选择第 $3$ 条领带，产生奇怪感 $3$

奇怪程度为 $3$。

但我们还可以继续减小奇怪程度：

• 第 $1$ 名员工选择第 $2$ 条领带，产生奇怪感 $1$
• 第 $2$ 名员工选择第 $3$ 条领带，产生奇怪感 $1$
• 第 $3$ 名员工选择第 $1$ 条领带，产生奇怪感 $0$

奇怪程度为 $1$。

因此 $C_4=1$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（1 pts）：$N \le 10$。
• Subtask 2（8 pts）：$N \le 2000$。
• Subtask 3（91 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $1 \le N \le 2 \times 10^5$。
• $1 \le A_i \le 10^9$。
• $1 \le B_j \le 10^9$。

说明

翻译自 第19回日本情報オリンピック　本選 A 長いだけのネクタイ。