31492번 - 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.

입력

The input consists of three lines. The first line contains the single integer $N$. The second line contains $N/2$ space-separated integers $a_1, a_2, \dots , 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$ space-separated integers $b_1, b_2, \dots , b_{N/2}$ representing the choices of the second team leader: during the 2ドルk$^th turn, the second leader chose the $b_k$^th remaining player.

출력

The output should contain two lines, each containing $N/2$ space-separated integers. The first line should contain the list $x_1, x_2, \dots , 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, \dots , 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 2ドルk$^th turn.

제한

• 2ドル \le N \le 4,円 000,円 000$
• $N$ is a multiple of 2ドル$
• the choices of the team leaders are valid: at each step, they are between 1ドル$ and the number of remaining players (inclusive).

힌트