E. Grid Coloring
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

There is a grid with $$$2$$$ rows and $$$n$$$ columns, where the rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. There are $$$2n$$$ colors numbered from $$$1$$$ to $$$2n$$$. Some cells in the grid have already been colored, and you need to color the remaining cells (cells that have already been colored cannot be recolored) in such a way that the number of four-connected components of the same color is minimized. Please construct a coloring scheme.

Four-connected means that if two cells of the same color share a common edge, then these two cells are considered connected.

Input

The first line contains an integer $$$n$$$ ($$$1\le n\le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_{1,1},a_{1,2},\ldots,a_{1,n}$$$ ($$$0\le a_{1,i}\le 2n$$$), representing the coloring of the first row of the grid.

The third line contains $$$n$$$ integers $$$a_{2,1},a_{2,2},\ldots,a_{2,n}$$$ ($$$0\le a_{2,i}\le 2n$$$), representing the coloring of the second row of the grid.

If $$$a_{i,j}=0$$$, it means that the cell in the $$$i$$$-th row and $$$j$$$-th column is not colored, otherwise it represents the color of the cell in the $$$i$$$-th row and $$$j$$$-th column as $$$a_{i,j}$$$. It is guaranteed that at least one cell is initially colored ($$$a_{i,j}\neq 0$$$).

Output

Output two lines, each containing $$$n$$$ positive integers $$$b_{i,j}$$$ ($$$1\le b_{i,j}\le 2n$$$), representing a coloring scheme. The output should ensure that cells that have already been colored cannot be recolored, i.e., for cells where $$$a_{i,j}\neq 0$$$, the output should ensure that $$$b_{i,j}=a_{i,j}$$$.

If there are multiple valid coloring schemes, output any one of them.

Examples
Input
5
1 0 1 0 2
3 3 2 0 4
Output
1 1 1 2 2 
3 3 2 2 4
Input
6
1 0 4 0 2 3
4 0 1 2 0 3
Output
1 4 4 2 2 3 
4 4 1 2 3 3
Input
6
1 0 2 0 0 0
3 0 0 0 4 1
Output
1 1 2 1 1 1 
3 1 1 1 4 1