题目描述

A snake fills a board completely.

Successive segments of the snake are numbered from to .

The segments with successive numbers (i.e., 1 and 2, 2 and 3, 3 and 4...) occupy squares that share an edge.

For example, a snake can fill a board as follows:

The snake's segment numbers in some of the squares have been erased.

Can you reconstruct the snake?

一只蛇被放在了一块3*n的木板上（填充满了），蛇被分为多个小段，小段的编号是1到3n。比如说蛇可以填写一个3*9的木板，如下所示：

部分木板上的蛇段已删遮挡。

你能重建蛇吗？

输入格式

In the first line of the standard input, there is a single integer (), the length of the board.

The three lines that follow describe the board; the -th of them contains integers ( for ).

If , then is the number of the snake's segment occupying the -th square of the -th row of the board.

If on the other hand , then the number of the snake's segment on this square is unknown.

In tests worth 15% of the total score holds, in those worth 40% of the total score holds, and finally, in those worth 70% of the total score holds.

在标准输入的第一行中，有一个整数n（1<=n<=1000），即板的长度。

下面三行描述木板的情况，第i行是n个整数aij（0<=aij<=3n）(1<=j<=n)。

如果aij大于0，那么aij就是蛇段的第aij部分

如果aij=0，那么这个蛇段就是我们不知道的

输出格式

Your program is to print three lines to the standard output.

The -th lines should hold positive integers (for ).

All the numbers together should be a permutation of the numbers from to .

The output numbers should be a valid reconstruction of the snake, i.e., they should be consistent with the (positive) input numbers and satisfy aforementioned constraints.

You may assume that there is at least one valid reconstruction of the snake.

If there is more than one, your program can print any valid reconstruction.

将所有aij为0的蛇段补齐

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