CF2172J.Sliding Tiles

You have a special sliding puzzle played on an $n \times n$ grid. This puzzle is slightly different from standard sliding puzzles: between each pair of adjacent columns, there is a vertical bar of height $h_i$ (for $1 \leq i \lt n$) positioned at the bottom of the grid. Each $h_i$ indicates how many rows from the bottom this bar extends upwards, and it blocks tile movement between the two columns in those rows.

The grid contains several tiles, each occupying exactly one cell. These tiles can slide freely in the grid unless they are blocked by the grid boundaries, a vertical bar (depending on its height) or another tile.

The puzzle allows two types of tilt operations:

• Tilt right: All tiles slide to the right as far as possible.
• Tilt down: All tiles slide downward as far as possible.

In both operations, all tiles move simultaneously and stop only when blocked by the grid's edge, a bar, or another tile.

Figure 1: An illustration for sample input 1.

Define a group operation as a sequence of: first tilt the grid to the right, then tilt it downward.

Initially, the $i$-th column has $a_i$ tiles stacked from the bottom of the column. You perform the group operation exactly once on the board. After the operation, determine the number of tiles in each column.

你有一个特殊的滑动拼图，它在一个 $n \times n$ 的网格上进行。该拼图与标准滑动拼图略有不同：在每对相邻列之间，网格底部设有一根高度为 $h_i$（其中 $1 \leq i < n$）的垂直挡板。每个 $h_i$ 表示该挡板从网格底行向上延伸的行数，并在这些行中阻止瓷砖在两列之间移动。

网格中放置若干瓷砖，每块瓷砖恰好占据一个格子。这些瓷砖可在网格中自由滑动，除非被网格边界、垂直挡板（取决于其高度）或其它瓷砖阻挡。

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

• 向右倾转：所有瓷砖尽可能向右滑动。
• 向下倾转：所有瓷砖尽可能向下滑动。

在上述两种操作中，所有瓷砖同时移动，并仅在碰到网格边缘、挡板或其它瓷砖时停止。

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

定义一次“组操作”为如下序列：先向右倾转网格，再向下倾转网格。

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

The first line contains an integer $n$, representing the size of the board.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, where $a_i$ is the number of tiles in the $i$-th column initially.

The third line contains $n-1$ integers $h_1,h_2,\ldots,h_{n-1}$, where $h_i$ is the height of the bar between column $i$ and column $i+1$.

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

第一行包含一个整数 $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$

Print $n$ numbers in a new line, representing the number of tiles in each column after performing the group operation exactly once.

在执行一次分组操作后，每列中的方块数量，共输出 $n$ 个数字，每个数字占一行。