You are the teacher of a class of n² pupils at an elementary school. Seats in the classroom are set up in a square shape of n rows (row 1 through row n) by n columns (column 1 through column n).

You are planning a change in the sitting arrangement. In order for your pupils to interact with many different pupils, you want to make those currently on adjacent seats have remote seats.

There is at least one sitting arrangement such that every pair of pupils currently on adjacent seats have seats with the Manhattan distance of no less than ⌊n / 2⌋ between them. Your task is to find such an arrangement. Here, ⌊x⌋ represents the largest integer less than or equal to x. The Manhattan distance of two seats are the sum of the absolute difference of their row numbers and that of their column numbers. Adjacent seats mean those with the Manhattan distance 1.

For example, in the first dataset of Sample Input (n = 4), pupils at the four adjacent seats of the pupil no. 10 are those numbered 6, 9, 11, and 14. In the Output for the Sample Input corresponding to this, their seats have Manhattan distances 3, 3, 2, and 3 from the seat of the pupil no. 10, all of which are ⌊ 4 / 2 ⌋ = 2 or greater. This condition also holds for all the other pupils.

The input consists of multiple datasets, each in the format below. The number of datasets does not exceed 50.

n
a₁₁ a₁₂ ⋯ a_1n
a₂₁ a₂₂ ⋯ a_2n
 ⋮
a_n1 a_n2 ⋯ a_nn

Here, n is the number of rows and also columns of the seats in the classroom (2 ≤ n ≤ 50). The following n lines denote the current sitting arrangement. Each a_ij gives the ID number of the pupil currently sitting in the i-th row from the back and the j-th column from the left, as seen from the teacher's desk. a_ij's are integers 1 through n², without duplicates.

The end of the input is indicated by a line consisting of a single zero.

For each dataset, output a sitting arrangement satisfying the condition stated above in the same format as in the input. If there are two or more such arrangements, any of them will do.

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
7
1 8 15 22 29 36 43
2 9 16 23 30 37 44
3 10 17 24 31 38 45
4 11 18 25 32 39 46
5 12 19 26 33 40 47
6 13 20 27 34 41 48
7 14 21 28 35 42 49
0

6 1 14 8
16 13 11 9
4 10 2 12
5 3 15 7
4 20 18 44 12 16 36
23 38 40 48 7 39 26
29 9 14 35 37 2 49
13 46 30 5 45 43 24
42 33 17 22 19 27 47
1 3 21 25 11 15 41
31 6 8 34 28 32 10