Team selection

Two team leaders get to assemble their teams by choosing team members among a set of players that are numbered from $1$ to $n$. The leaders take turns, each picking the $k$-th player among the remaining ones, according to their ideas of which one of the remaining players would be the best addition to their teams.

Given the choices of the two leaders (the first team leader starts first), please compute the list of players in each team.

Giriş verilənləri

Consists of three lines.

The first line contains the single integer $n(2\le n\le 4\cdot 10^6$, $n$ is a multiple of $2$).

The second line contains $n/2$ integers $a_1,a_2,...,a_{n/2}$ representing the choices of the first team leader: during the $(2k-1)$-th turn, the first leader chose the $a_k$-th remaining player.

The third line contains $n/2$ integers $b_1,b_2,...,b_{n/2}$ representing the choices of the second team leader: during the $2k$-th turn, the second leader chose the $b_k$-th remaining player.

The choices of the team leaders are valid: at each step, they are between $1$ and the number of remaining players (inclusive).

Çıxış verilənləri

Print two lines, each containing $n/2$ integers.

The first line should contain the list $x_1,x_2,...,x_{n/2}$ of the players chosen to become members of the first team, in the order they were chosen: the player $x_k$ was chosen during the $(2k-1)$-th turn.

The second line should contain the list $y_1,y_2,...,y_{n/2}$ of the players chosen to become members of the second team, in the order they were chosen: the player $y_k$ was chosen during the $2k$-th turn.

Nümunələr