Find the Pairs

Time Limit: 1 Second    Memory Limit: 32768 KB

"Find the pairs" is a puzzle game played on a 4 * 4 board. The 16 grids are colored in pairs with 8 diffrent colors. The player is supposed to look at the board for 20 seconds and try to remember the color of the grids. Then each grid is turned over and the player shall turn two grids over in each move. If the two grids are not of the same color, they are turned over again, otherwise not. The player's goal is to turn all grids over in as few moves as possible.

Not many people can reach the goal in just 8 moves, because there's so much to remember. To help people solve such puzzles, a method is developed to encode the square first, thus enables people to remember less things than before. It works as follows:

Let's just consider the above puzzle for example. We first find the grid that has the same color as the grid in row 1 column 1 and mark it with "1". Then we find the grid with the same color as the grid in row 2 column 1 and mark it with "2". We keep marking the grids from top to bottom, left to right. If we reach a grid that has already been marked, just skip it. It is immediate result that after such process, exactly 8 grids are marked with distinct numbers between 1 and 8. It is also not difficult to see that, with the positions of the 8 numbers given, we can successfully restore the original arrangement of the pairs.

Pity that some players have got really bad memory! Even with this encoding method, sometimes they may just remember the positions of somes of the numbers and forget the others. However,there's good news: with some of the numbers remembered, we may sometimes deduce numbers in other positions, and it is what your program should do.

Input

The input contains several cases. Each case begins with an even interger N (0 <= N <= 20), the size of the square. N lines follow, each contains N integers, describing the corresponding row with adjacent numbers seperated by a single space. "-1" means an unmarked grid, "0" means a marked grid but the number marked with is forgotten, an integer between 1 and N * N / 2 means that the grid is marked with this integer. There are exactly N * N / 2 "-1"s, and for any number between 1 and N * N / 2, inclusively, it appears at most once. Input is terminated by a case with N = 0, which should not be processed.

Output

For each test case, output the original numbers with the same format as stated in the input except for the marked grids whose values can be uniquely deduced, print the value instead of 0. To make things worse, the player may even forget the positions of the marked grids, sometimes making it impossible to get the given input by encoding any original squares. In such cases,print a single line with the number "-1". Print a blank line after each test case.

Sample Input

4
-1 3 0 5
-1 1 -1 -1
-1 -1 7 4
-1 -1 2 0
4
-1 3 6 5
-1 0 -1 -1
-1 -1 7 4
-1 0 2 -1
0

Sample Output

-1 3 6 5
-1 1 -1 -1
-1 -1 7 4
-1 -1 2 8

-1

Submit

Source: ZOJ Monthly, March 2004