小学校の教師であるあなたは n² 人からなるクラスの担任をしている． 教室の席は n 行 (行番号 1 から n)，n 列 (列番号 1 から n) の正方形に並んでいる．

あなたは席替えを考えている． 生徒にはいろいろな生徒と交流して欲しいので，いま隣り合っている生徒同士は遠い席になるようにしたい．

席がいま隣り合っているどの 2 人の生徒についても，新しい席のマンハッタン距離が ⌊n / 2⌋ 以上になるような席の配置が少なくとも 1 つある． そのような配置を 1 つ見つけて欲しい． ここで ⌊x⌋ は x 以下の最大の整数を表す． 2 つの席の間のマンハッタン距離とは，両者の行番号の差の絶対値と列番号の差の絶対値を足し合わせたものである． また，隣り合う席とはマンハッタン距離が 1 の席同士のことをいう．

たとえば，Sample Input の最初のデータセット (n = 4) で，10 番の生徒の隣には，6, 9, 11, 14 番の 4 人の生徒がいる． これら 4 人の席替え後 (Output for the Sample Input) の 10 番からのマンハッタン距離は，それぞれ 3, 3, 2, 3 で，いずれも ⌊ 4 / 2 ⌋ = 2 以上になっている． 他のどの生徒についても，条件が満たされている．

入力は複数のデータセットからなり，各データセットは以下の形式で表される． データセットの個数は 50 を超えない．

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

ここで n は教室の席の行の数であり列の数でもある (2 ≤ n ≤ 50)． 続く n 行は現在の席の配置を表す． 各 a_ij は，教卓から見て奥から i 番目の列，左から j 番目の行の席に座っている生徒の出席番号である． a_ij は 1 から n² までの整数であり，重複はない．

入力の終わりは，ゼロだけからなる行で表される．

各データセットについて，上述の条件を満たす席の配置を入力中の席の配置と同じ形式で出力せよ． 条件を満たす配置が複数ある場合は，どれを答えても良い．

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