Problem D
Snake

Yesterday, little Olle won the famous game Snake for the first time. In Snake, there is a $3 \times N$ grid. The player controls a snake consisting of several segments. Initially, the snake consists of a single segment, which we call its head. Every second, the head can move up, down, left, or right. If the head collides with another segment, the game is lost. After the head moves, the snake loses the segment furthest from the head (the oldest segment belonging to the snake). In other words, one can imagine the snake’s body moving one square. During the game, apples will appear on certain squares. If the snake’s head enters a square with an apple, the apple disappears, but the segment furthest from the head does not disappear. In other words, the snake’s length increases by $1$.

If the snake fills up the entire grid, the game is won because the snake cannot grow any longer. When Olle wants to brag to his friends that he finally won Snake, they don’t believe him. To convince his friends, Olle plans to draw how his snake looked when he won. Unfortunately, he doesn’t remember exactly how it looked. However, he remembers how far certain squares were from the tail (the segment furthest from the head). Given some of these distances, can you find out how Olle’s snake looked?

Figure 1: The picture the snake looks like in sample 1. For this grid, this is the only valid snake.

Input

The first line contains the integer $N$ ($1 \leq N \leq 1000$), the number of columns in the grid.

Following that are three lines, each describing a row of the grid. The $i$-th row contains the integers $c_1, c_2, \dots , c_ N$ ($0 \leq c_ j \leq c_ N$), representing the distance between the tail and the snake’s body segment at row $i$ and column $j$. If $c_ j$ is $0$, it means Olle forgot what $c_ j$ is. All $c_ j$ that are not $0$ are pairwise unique. It is also guaranteed that there is at least one valid solution.

Output

Print $3$ lines with $N$ integers each, describing a valid winning snake. Each integer between $1$ and $N \cdot 3$ must occur exactly once. For each $i$ between $1$ and $N \cdot 3 - 1$, the segment with number $i$ must be above, below, to the left, or to the right relative to the segment with number $i+1$. If there are multiple valid snakes, you can print any valid snake.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

5
3 2 0 10 11
4 0 8 15 12
0 0 0 14 0

3 2 9 10 11
4 1 8 15 12
5 6 7 14 13

6
0 0 0 0 0 0
4 3 16 15 14 11
5 6 7 8 9 10

1 2 17 18 13 12
4 3 16 15 14 11
5 6 7 8 9 10