#2232. Snake

Snake

Snake

题目描述

标题: Snake - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

A snake fills a 3×n board completely. Successive segments of the snake are numbered from 1 to 3n. 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 3×9 board as follows:

The snake's segment numbers in some of the squares have been erased. Can you reconstruct the snake?

Input Format

In the first line of the standard input, there is a single integer n (1≤n≤1000), the length of the board. The three lines that follow describe the board; the i-th of them contains n integers aij (0≤aij≤3n for 1≤j≤n). If aij>0, then aij is the number of the snake's segment occupying the j-th square of the i-th row of the board. If on the other hand aij=0, then the number of the snake's segment on this square is unknown.

Output Format

Your program is to print three lines to the standard output. The i-th lines should hold n positive integers bij (for 1≤j≤n). All the numbers bij together should be a permutation of the numbers from 1 to 3n. 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.

Example

Input

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

Output

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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