import std.conv, std.functional, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } int N; int[][] A; int calc(in int[][] a) { int s; int[] perm; foreach (x; 0 .. N) foreach (y; 0 .. N) { if (1 <= a[x][y] && a[x][y] <= N^^2 - 1) { perm ~= a[x][y]; } } foreach (i; 0 .. perm.length) foreach (j; i + 1 .. perm.length) { if (perm[i] > perm[j]) { s ^= 1; } } foreach (x; 0 .. N) foreach (y; 0 .. N) { if (a[x][y] == 0 || a[x][y] == N^^2) { s ^= (x & 1); } } return s; } void main() { try { for (; ; ) { N = readInt(); A = new int[][](N, N); foreach (x; 0 .. N) foreach (y; 0 .. N) { A[x][y] = readInt(); } // foreach(N;3..51){A=new int[][](N,N); if (N == 2) { writeln("impossible"); continue; } auto a = new int[][](N, N); if (N % 4 == 0) { foreach (x; 0 .. N) foreach (y; 0 .. N) { a[x][y] = x * N + y; } foreach (x; 0 .. N / 2) foreach (y; 0 .. N) { if ((popcnt(x & 3) - popcnt(y & 3)) % 2 != 0) { swap(a[x][y], a[N - 1 - x][N - 1 - y]); } } } else if (N % 4 == 2) { auto b = new int[][](N / 2, N / 2); foreach (i; 0 .. N / 2) foreach (j; 0 .. N / 2) { const x = -(N / 2) / 2 + i + j; const y = (N / 2) / 2 - i + j; b[(x + N / 2) % (N / 2)][(y + N / 2) % (N / 2)] = i * (N / 2) + j; } foreach (x; 0 .. N / 2) foreach (y; 0 .. N / 2) { int[][] c; if (x < (N / 2) / 2) { c = [[3, 0], [1, 2]]; } else if (x == (N / 2) / 2) { c = (y != (N / 2) / 2) ? [[3, 0], [1, 2]] : [[0, 3], [1, 2]]; } else if (x == (N / 2) / 2 + 1) { c = (y == (N / 2) / 2) ? [[3, 0], [1, 2]] : [[0, 3], [1, 2]]; } else { c = [[0, 3], [2, 1]]; } foreach (dx; 0 .. 2) foreach (dy; 0 .. 2) { a[x * 2 + dx][y * 2 + dy] = b[x][y] * 4 + c[dx][dy]; } } } else { foreach (i; 0 .. N) foreach (j; 0 .. N) { const x = -N / 2 + i + j; const y = N / 2 - i + j; a[(x + N) % N][(y + N) % N] = i * N + j; } } /* int s0, s1, s2; foreach (x0; 0 .. N) foreach (y0; 0 .. N) { foreach (x1; 0 .. N) foreach (y1; 0 .. N) { if (a[x0][y0] != N^^2 - 1 && a[x1][y1] != N^^2 - 1 && [x0, y0] < [x1, y1] && a[x0][y0] > a[x1][y1]) { s0 ^= 1; } } } foreach (x; 0 .. N) foreach (y; 0 .. N) { if (a[x][y] == N^^2 - 1) { s0 ^= (x & 1); } } foreach (x0; 0 .. N) foreach (y0; 0 .. N) { foreach (x1; 0 .. N) foreach (y1; 0 .. N) { if (a[x0][N - 1 - y0] != N^^2 - 1 && a[x1][N - 1 - y1] != N^^2 - 1 && [x0, y0] < [x1, y1] && a[x0][N - 1 - y0] > a[x1][N - 1 - y1]) { s1 ^= 1; } } } foreach (x; 0 .. N) foreach (y; 0 .. N) { if (a[x][N - 1 - y] == N^^2 - 1) { s1 ^= (x & 1); } } foreach (x0; 0 .. N) foreach (y0; 0 .. N) { foreach (x1; 0 .. N) foreach (y1; 0 .. N) { if (a[y0][x0] != N^^2 - 1 && a[y1][x1] != N^^2 - 1 && [x0, y0] < [x1, y1] && a[y0][x0] > a[y1][x1]) { s2 ^= 1; } } } foreach (x; 0 .. N) foreach (y; 0 .. N) { if (a[y][x] == N^^2 - 1) { s2 ^= (x & 1); } } debug { writefln("N = %2d: %s %s %s", N, s0, s1, s2); stdout.flush; } */ foreach (x; 0 .. N) foreach (y; 0 .. N) { ++a[x][y]; } const sA = calc(A); const sa = calc(a); if (sA != sa) { if (N % 4 == 1) { foreach (x; 0 .. N) foreach (y; 0 .. N) { if (x < y) { swap(a[x][y], a[y][x]); } } } else { foreach (x; 0 .. N) { a[x].reverse; } } } assert(sA == calc(a)); writeln("possible"); foreach (x; 0 .. N) { writeln(a[x].to!string.replaceAll(regex(`[\[\],]`), "")); } const sum = a[0].sum; foreach (x; 0 .. N) { assert(sum == a[x].sum); } foreach (y; 0 .. N) { assert(sum == iota(N).map!(x => a[x][y]).sum); } assert(sum == iota(N).map!(x => a[x][x]).sum); assert(sum == iota(N).map!(x => a[x][N - 1 - x]).sum); } } catch (EOFException e) { } }