#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } void oddMagicSquare(int N, vector &a) { int i = 0, j = N / 2; a.assign(N, vi(N)); int sqr = N * N; rer(k, 1, sqr) { a[i][j] = k; -- i, ++ j; if(k % N == 0) { i += 2; -- j; }else { if(j == N) { j -= N; }else if(i < 0) { i += N; } } } } void magicSquare(int N, vector &a) { if(N % 2 == 1) { oddMagicSquare(N, a); }else if(N % 4 == 0) { a.assign(N, vi(N)); vector I(N, vi(N, 0)), J = I; int k = 1; rep(i, N) rep(j, N) a[i][j] = k ++; rep(i, N) rep(j, N) if((i + 1) % 4 / 2 == (j + 1) % 4 / 2) a[i][j] = N * N + 1 - a[i][j]; }else { a.assign(N, vi(N)); int p = N / 2, pp = p * p; vector M; oddMagicSquare(p, M); rep(i, p) rep(j, p) { a[i][j] = M[i][j]; a[i+p][j] = M[i][j] + 3*pp; a[i][j+p] = M[i][j] + 2*pp; a[i+p][j+p] = M[i][j] + pp; } vi I(p, 0), J; rep(i, p) I[i] = i+1; int k = (N - 2) / 4; rep(i, k) J.push_back(i); reu(i, N - k + 1, N) J.push_back(i); rep(i, p) rep(j, J.size()) swap(a[i][J[j]], a[i+p][J[j]]); swap(a[k][0], a[k+p][0]); swap(a[k][k], a[k+p][k]); } } bool getParity(const vector &perm) { int n = perm.size(); vector vis(n); bool p = false; rep(i, n) if(!vis[i]) { int j = i; int len = 0; while(!vis[j]) { vis[j] = true; j = perm[i]; ++ len; } if(len % 2 == 0) p = !p; } return p; } bool getSlidingParity(const vector &A, const vector &B) { int h = A.size(), w = A[0].size(); vi pos(h * w), perm(h * w); rep(i, h) rep(j, w) pos[B[i][j] - 1] = i * w + j; int dist = 0; rep(i, h) rep(j, w) { int p = pos[A[i][j] - 1]; perm[i * w + j] = p; if(A[i][j] % (h * w) == 0) dist += abs(p / w - i) + abs(p % w - j); } bool p = getParity(perm); bool q = dist % 2 != 0; return p != q; } int main() { int N; while(cin >> N) { vector A(N, vi(N)); rep(i, N) rep(j, N) { scanf("%d", &A[i][j]); if(A[i][j] == 0) A[i][j] = N * N; } if(N == 2) { puts("impossible"); continue; } vector org; magicSquare(N, org); vector board = org; rep(yx, 2) { rep(x, 2) { rep(y, 2) { if(!getSlidingParity(A, board)) goto ok; reverse(all(board)); } rep(i, N) reverse(all(board[i])); } rep(i, N) rep(j, N) board[j][i] = org[i][j]; } if(0) { ok:; puts("possible"); rep(i, N) { rep(j, N) { if(j != 0) putchar(' '); printf("%d", board[i][j]); } puts(""); } }else { return 1; puts("impossible"); } } return 0; }