intgetn(int N) { int res = 1; for(int i = 0; i < N; i++) res *= 2; return res; }
voidrescue(int sx, int sy, int ex, int ey) { if(sx == ex && sy == ey) return; int X = ex - sx, Y = ey - sy; for(int i = sy; i < sy + Y / 2 + 1; i++) for(int j = sx; j < sx + X / 2 + 1; j++) prisoner[i][j] = 0;
rescue(sx + X / 2 + 1, sy, ex, sy + Y / 2); rescue(sx, sy + Y / 2 + 1, sx + X / 2, ey); rescue(sx + X / 2 + 1, sy + Y / 2 + 1, ex, ey); }
intmain(int argc, constchar * argv[]) { int N; cin >> N; n = getn(N); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) prisoner[i][j] = 1; rescue(0, 0, n - 1, n - 1); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { cout << prisoner[i][j]; if(j < n - 1) cout << " "; else cout << endl; }