import sys import numpy as np read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines def f(N): if N % 4 == 0: return f0(N) elif N % 4 == 2: return f2(N) else: return f13(N) def f13(N): A = np.zeros((N, N), np.int32) x = 0 y = N // 2 for i in range(1, N * N + 1): if A[x][y]: x += 2 y -= 1 x %= N y %= N A[x, y] = i x -= 1 y += 1 x %= N y %= N return A def f0(N): A = np.arange(N * N).reshape(N, N) A[1::4, 0::4] *= -1 A[1::4, 3::4] *= -1 A[2::4, 0::4] *= -1 A[2::4, 3::4] *= -1 A[0::4, 1::4] *= -1 A[0::4, 2::4] *= -1 A[3::4, 1::4] *= -1 A[3::4, 2::4] *= -1 A[A < 0] += N * N - 1 A += 1 return A def f2(N): A = f(N // 2) A = np.repeat(A, 2, axis=0).repeat(2, axis=1) A = (A - 1) * 4 n = N // 4 # L-type A[:2 * n + 2:2, ::2] += 4 A[:2 * n + 2:2, 1::2] += 1 A[1:2 * n + 2:2, ::2] += 2 A[1:2 * n + 2:2, 1::2] += 3 # U-type A[2 * n + 2, ::2] += 1 A[2 * n + 2, 1::2] += 4 A[2 * n + 3, ::2] += 2 A[2 * n + 3, 1::2] += 3 # X-type A[2 * n + 4::2, ::2] += 1 A[2 * n + 4::2, 1::2] += 4 A[2 * n + 5::2, ::2] += 3 A[2 * n + 5::2, 1::2] += 2 # modify center A[2 * n, 2 * n] -= 3 A[2 * n, 2 * n + 1] += 3 A[2 * n + 2, 2 * n] += 3 A[2 * n + 2, 2 * n + 1] -= 3 return A N = int(readline()) A = np.array(read().split()).reshape(N, N).astype(np.int8) def check(A, B): N = A.shape[0] A = A.ravel() B = B.ravel() Ax, Ay = np.divmod(np.argmax(A), N) Bx, By = np.divmod(np.argmax(B), N) pos_A = np.empty_like(A) pos_A[A] = np.arange(N * N) B = pos_A[B] inv = 0 for i, x in enumerate(B): inv += np.sum(B[:i] > x) dist = abs(Ax-Bx) + abs(Ay-By) return (inv - dist) % 2 == 0 def solve(A): N = A.shape[0] if N == 1: return A if N == 2: return None if N == 3: B = f(N) - 1 if check(A, B): return B else: return None if N % 2 == 0: B = f(N) - 1 if check(A, B): return B else: return B[::-1] if N % 3 != 0: # 完全方陣 x = np.arange(N) B0 = np.add.outer(x, 2 * x) % N B1 = B0.T B = N * B0 + B1 if check(A, B): return B return np.roll(B, axis=0) # N は 3 の倍数 M = N // 3 C = (f(M) - 1) * 9 D = f(3) - 1 B = np.empty_like(A) for i in range(3): for j in range(3): B[i::3, j::3] = C + D[i, j] if check(A, B): return B x, y = divmod(np.argmax(C), M) temp = B[3 * x, 3 * y:3 * y + 3].copy() B[3 * x, 3 * y:3 * y + 3] = B[3 * x + 2, 3 * y:3 * y + 3] B[3 * x + 2, 3 * y:3 * y + 3] = temp return B A[A == 0] = N * N A -= 1 B = solve(A) if B is None: print('impossible') else: print('possible') B += 1 print('\n'.join(' '.join(row) for row in B.astype(str)))