Description

A snake fills a $3 \times n$ board completely. The snake is divided into segments numbered from $1$ to $3n$. Consecutive segments (i.e., $k$ and $k+1$) must occupy squares that share an edge. Some segment numbers on the board are erased. Can you reconstruct the snake?

Constraints: $1 \le n \le 1000$.

Description

Input Format

The first line contains an integer $n$ ($1 \le n \le 1000$), the length of the board.

The next three lines describe the board. The $i$-th of these lines contains $n$ integers $a_{i j}$ ($0 \le a_{i j} \le 3n$) for $1 \le j \le n$.

If $a_{i j} > 0$, then $a_{i j}$ is the number of the snake’s segment occupying the $j$-th square of the $i$-th row. If $a_{i j} = 0$, then the number on this square is unknown.

It is guaranteed that there is at least one valid reconstruction.

Output Format

Print three lines. The $i$-th line should contain $n$ positive integers $b_{i j}$ ($1 \le j \le n$).

All numbers $b_{i j}$ together must form a permutation of $1, 2, \dots, 3n$. For every $(i, j)$ with $a_{i j} > 0$, it must hold that $b_{i j} = a_{i j}$. Moreover, for every $k$ from $1$ to $3n-1$, the squares containing $k$ and $k+1$ must share an edge.

If multiple solutions exist, output any of them.

9
0 0 5 0 17 0 0 0 21
8 0 0 3 16 0 0 25 0
0 0 0 0 0 0 0 0 23

7 6 5 4 17 18 19 20 21
8 1 2 3 16 15 26 25 22
9 10 11 12 13 14 27 24 23

Hint

Translated by ChatGPT 5