您在 $$$n \times n$$$ 网格上玩了一个特殊的滑动谜题。这个谜题与标准滑动谜题略有不同:在每对相邻的列之间,有一个高度为 $$$h_i$$$ 的垂直条(对于 $$$1 \leq i \lt n$$$)位于网格底部。每个 $$$h_i$$$ 表示该条从底部向上延伸了多少行,并且它阻止了这些行中两列之间的图块移动。
网格包含多个图块,每个图块正好占据一个单元格。这些图块可以在网格中自由滑动,除非它们被网格边界、垂直条(取决于其高度)或另一个图块阻挡。
拼图允许两种类型的倾斜操作:
- 向右倾斜:所有图块尽可能向右滑动。
- 向下倾斜:所有瓷砖尽可能向下滑动。
在这两种操作中,所有图块同时移动,并且仅在被网格边缘、条形或其他图块阻挡时才停止。
图 1:示例输入 1 的图示。 将组操作定义为以下序列:首先将网格向右倾斜,然后向下倾斜。
最初,第 $$$i$$$ 列有从该列底部堆叠的 $$$a_i$$$ 瓷砖。您只需在板上执行一次组操作即可。运算结束后,确定每列的图块数量。
输入
第一行包含一个整数$$$n$$$,代表棋盘的大小。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$,其中 $$$a_i$$$ 是最初第 $$$i$$$ 列中的图块数量。
第三行包含 $$$n-1$$$ 整数 $$$h_1,h_2,\ldots,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$$$ 数字,表示执行一次分组操作后每列中的图块数量。
示例
输入复制
55 5 2 3 03 0 4 1
输出复制
3 3 4 2 3
输入复制
64 3 0 3 0 21 0 0 1 3
输出复制
1 0 3 3 2 3