你正在玩一种特殊的滑动拼图，它在一个 $n \times n$ 的网格上进行。这个拼图与标准的滑动拼图略有不同：在每一对相邻的列之间，网格底部都有一个高度为 $h_i$（对于 $1 \le i < n$）的垂直挡板。每个 $h_i$ 表示该挡板从底部向上延伸的行数，它会阻挡这些行中两列之间的方块移动。

网格中包含若干方块，每个方块恰好占据一个单元格。除非被网格边界、垂直挡板（取决于其高度）或另一个方块阻挡，否则这些方块可以在网格中自由滑动。

该拼图允许两种倾斜操作：

• 向右倾斜：所有方块尽可能向右滑动。
• 向下倾斜：所有方块尽可能向下滑动。

在这两种操作中，所有方块同时移动，并且只有在被网格边缘、挡板或另一个方块阻挡时才会停止。

图 1：样例输入 1 的示意图。

定义一次“组合操作”为以下顺序：首先将网格向右倾斜，然后将其向下倾斜。

初始时，第 $i$ 列有 $a_i$ 个方块从该列底部向上堆叠。你对棋盘执行恰好一次组合操作。操作完成后，确定每一列中方块的数量。

输入格式

第一行包含一个整数 $n$，表示棋盘的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 是初始时第 $i$ 列中方块的数量。

第三行包含 $n - 1$ 个整数 $h_1, h_2, \dots, h_{n-1}$，其中 $h_i$ 是第 $i$ 列和第 $i + 1$ 列之间挡板的高度。

• $2 \le n \le 5 \times 10^5$
• $0 \le a_i \le n$
• $0 \le h_i \le n - 1$

输出格式

在一行中输出 $n$ 个数字，表示执行恰好一次组合操作后每一列中方块的数量。

样例

输入 1

5
5 5 2 3 0
3 0 4 1

输出 1

3 3 4 2 3

输入 2

6
4 3 0 3 0 2
1 0 0 1 3

输出 2

1 0 3 3 2 3