package q6xx; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.BitSet; import java.util.InputMismatchException; public class Q664_3 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { // for(int i = 1;i <= 12;i++){ // tr(i); // int[][] tw = panmagicX4(i*4, 1); //// tr(parity(tw)); // tr(ismagic(tw)); // } // if(true)return; int n = ni(); int[] a = na(n*n); int x = 0; for(int i = 0;i < n*n;i++){ if(a[i] == 0){ a[i] = n*n; x ^= ((i/n)^(i%n))&1; } } int parity = parity(a)^x; if(n == 1){ out.println("possible"); out.println(1); return; } if(n == 2){ out.println("impossible"); return; } out.println("possible"); int[][] ms = null; if(n % 2 == 1){ ms = what(n, parity); }else if(n % 4 == 2){ ms = what2(n, parity); }else{ ms = panmagicX4(n, parity); } if(!ismagic(ms)){ throw new RuntimeException(); } int tp = parity(ms); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(ms[i][j] == n*n){ tp ^= (i^j)&1; } } } if(tp != parity)throw new RuntimeException(); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(j > 0)out.print(" "); out.print(ms[i][j]); } out.println(); } } static int[][] what2(int n, int want) { n /= 2; int[] A = new int[n]; for(int i = 0;i < n;i++)A[i] = i; int[] B = new int[n]; for(int i = 0;i < n;i++)B[i] = i; do{ int[][] a = new int[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ a[i][j] = A[(i+j+n-n/2)%n]*n+B[(i+n-j+n/2)%n]+1; // a[i][j] = A[(i+j*0)%n]; // a[i][j] = B[(i+n-j+n/2)%n]; // a[i][j] = (i*(n-s)+j+2)%n; } } if(!ismagic(a))continue; a = constructByLUXMethod(a); if(!ismagic(a))throw new RuntimeException(); int lp = -1; for(int i = 0;i < a.length;i++){ for(int j = 0;j < a.length;j++){ if(a[i][j] == 4*n*n)lp = (i^j)&1; } } if(lp == -1)throw new RuntimeException(); if(parity(a) == (want^lp))return a; }while(nextPermutation(B)); return null; } static int[][] what(int n, int want) { int[] A = new int[n]; for(int i = 0;i < n;i++)A[i] = i; int[] B = new int[n]; for(int i = 0;i < n;i++)B[i] = i; do{ int[][] a = new int[n][n]; int lp = -1; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ a[i][j] = A[(i+j+n-n/2)%n]*n+B[(i+n-j+n/2)%n]+1; if(a[i][j] == n*n)lp = (i^j)&1; // a[i][j] = A[(i+j*0)%n]; // a[i][j] = B[(i+n-j+n/2)%n]; // a[i][j] = (i*(n-s)+j+2)%n; } } if(!ismagic(a))continue; if(lp == -1)throw new RuntimeException(); // if(!ismagic(a))throw new RuntimeException(); if(parity(a) == (want^lp))return a; }while(nextPermutation(B)); return null; } public static boolean nextPermutation(int[] a) { int n = a.length; int i; for (i = n - 2; i >= 0 && a[i] >= a[i + 1]; i--) ; if (i == -1) return false; int j; for (j = i + 1; j < n && a[i] < a[j]; j++) ; int d = a[i]; a[i] = a[j - 1]; a[j - 1] = d; for (int p = i + 1, q = n - 1; p < q; p++, q--) { d = a[p]; a[p] = a[q]; a[q] = d; } return true; } static boolean ismagic(int[][] a) { int n = a.length; BitSet bs = new BitSet(); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(a[i][j] <= 0 || a[i][j] > n*n)return false; bs.set(a[i][j]); } } if(bs.cardinality() != n*n)return false; // 1-base int S = n*(n*n+1)/2; for(int i = 0;i < n;i++){ int ls = 0; for(int j = 0;j < n;j++)ls += a[i][j]; if(ls != S)return false; } for(int i = 0;i < n;i++){ int ls = 0; for(int j = 0;j < n;j++)ls += a[j][i]; if(ls != S)return false; } { int ls = 0; for(int i = 0;i < n;i++)ls += a[i][i]; if(ls != S)return false; } { int ls = 0; for(int i = 0;i < n;i++)ls += a[n-1-i][i]; if(ls != S)return false; } return true; } static int parity(int[][] t) { int n = t.length; int[] u = new int[n*n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ u[i*n+j] = t[i][j]; } } return parity(u); } public static int[][] constructBySiameseMethod2(int n) { if(n <= 0 || n % 2 == 0)throw new RuntimeException(); int[][] ret = new int[n][n]; int r = n/2-1, c = n/2; for(int i = 1;i <= n*n;i++){ ret[r][c] = i; int nr = r-1, nc = c+1; if(nr < 0)nr += n; if(nc >= n)nc -= n; if(ret[nr][nc] != 0){ nr = r-2; nc = c; if(nr < 0)nr += n; } r = nr; c = nc; } return ret; } public static int parity(int[] a) { int x = 0; int n = a.length; for(int i = 0;i < n;i++){ if(i != a[i]-1){ int j = a[i]-1; int d = a[i]; a[i] = a[j]; a[j] = d; x ^= 1; } } return x; } public static int[][] constructMagicSquare(int n) { if(n < 0)throw new RuntimeException(); if(n % 4 == 0){ // 4m return constructX4(n); }else if(n % 2 == 1){ // 2m+1 return constructBySiameseMethod(n); }else{ // 4m+2 return constructByLUXMethod(constructBySiameseMethod(n/2)); } } public static int[][] panmagicX4(int n, int want) { int[][] ret = new int[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ int A = i%2 == 0 ? (j < n/2 ? 1+j : n-(j-n/2)) : (j < n/2 ? n-j : 1+(j-n/2)); int B = j%2 == 0 ? (i < n/2 ? n/2+1+i : n/2-(i-n/2)) : (i < n/2 ? n/2-i : n/2+1+(i-n/2)); ret[i][j] = A + n * B - n; } } int par = parity(ret); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(ret[i][j] == n*n){ par ^= (i^j)&1; } } } if(par != want){ for(int j = 1;j < n;j++){ for(int k = 0;k < n;k++){ int[][] nret = new int[n][n]; for(int i = 0;i < n;i++){ for(int l = 0;l < n;l++){ nret[(i+j)%n][(k+l)%n] = ret[i][l]; } } if(!ismagic(nret))throw new RuntimeException(); if(par == (parity(nret)^((j^k)&1))){ ret = nret; return ret; } } } // for(int j = 1;j < n;j++){ // int[][] nret = new int[n][]; // for(int i = 0;i < n;i++){ // nret[(i+j)%n] = ret[i]; // } // if(!ismagic(nret))throw new RuntimeException(); // if(par == (parity(nret)^(j&1))){ // ret = nret; // return ret; // } // } throw new RuntimeException(); } return ret; } public static int[][] constructX4(int n) { if(n < 0 || n % 4 != 0)throw new RuntimeException(); int[][] ret = new int[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ int p = (i^j)&3; if(p == 0 || p == 3){ ret[i][j] = i*n+j+1; }else{ ret[i][j] = n*n-(i*n+j); } } } return ret; } public static int[][] constructByLUXMethod(int[][] a) { int n = a.length; if(n <= 0 || n % 2 == 0)throw new RuntimeException(); int[][] ret = new int[2*n][2*n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ int base = a[i][j]-1<<2; if(i > n/2+1){ // X ret[i*2][j*2] = base + 1; ret[i*2][j*2+1] = base + 4; ret[i*2+1][j*2] = base + 3; ret[i*2+1][j*2+1] = base + 2; }else if(j != n/2 && i <= n/2 || j == n/2 && i <= n/2+1 && i != n/2){ // L ret[i*2][j*2] = base + 4; ret[i*2][j*2+1] = base + 1; ret[i*2+1][j*2] = base + 2; ret[i*2+1][j*2+1] = base + 3; }else{ // U ret[i*2][j*2] = base + 1; ret[i*2][j*2+1] = base + 4; ret[i*2+1][j*2] = base + 2; ret[i*2+1][j*2+1] = base + 3; } } } return ret; } // val(i,j)=n*((i+j+1+n/2))%n)+(i+2*j+1)%n+1 TODO public static int[][] constructBySiameseMethod(int n) { if(n <= 0 || n % 2 == 0)throw new RuntimeException(); int[][] ret = new int[n][n]; int r = 0, c = n/2; for(int i = 1;i <= n*n;i++){ ret[r][c] = i; int nr = r-1, nc = c+1; if(nr < 0)nr += n; if(nc >= n)nc -= n; if(ret[nr][nc] != 0){ nr = r+1; nc = c; if(nr >= n)nr -= n; } r = nr; c = nc; } return ret; } public static boolean check(int[][] a) { int n = a.length; int[] f = new int[n*n+1]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(a[i][j] < 0 || a[i][j] > n*n)return false; if(++f[a[i][j]] > 1)return false; } } int base = n*(n*n+1)/2; // row for(int i = 0;i < n;i++){ int s = 0; for(int j = 0;j < n;j++)s += a[i][j]; if(s != base)return false; } // col for(int i = 0;i < n;i++){ int s = 0; for(int j = 0;j < n;j++)s += a[j][i]; if(s != base)return false; } // diagonal { int s = 0; for(int j = 0;j < n;j++)s += a[j][j]; if(s != base)return false; } { int s = 0; for(int j = 0;j < n;j++)s += a[n-1-j][j]; if(s != base)return false; } return true; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); } public static void main(String[] args) throws Exception { new Q664_3().run(); } private byte[] inbuf = new byte[1024]; private int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }