#include<bits/stdc++.h>
#include"prison.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VII;
const int maxn=333333,mod=998244353;
#define all(v) v.begin(),v.end()
#define sz(v) (int)(v.size())
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
const int d=9,sz[d]={2,2,3,3,2,3,2,2,1};
int at[11][11],cnt,bit[11][5555];
bool vis[11];
void dfs(int l,int r,int dep){
	if(l>=r) return;
//	printf("%d %d %d\n",l,r,dep);
	bit[dep][l]=-1;bit[dep][r]=-2;
	l++;r--;
	if(l>r) return;
	int c=r-l+1;
	FOR(i,0,sz[dep]-1){
		int tmp=c/sz[dep]+(i<c%sz[dep]);
		FOR(j,l,l+tmp-1) bit[dep][j]=i;
		dfs(l,l+tmp-1,dep+1);
		l+=tmp;
	}
}
VII devise_strategy(int N){
	MEM(bit,-1);
	dfs(0,N-1,0);
	FOR(i,0,d-1) FOR(j,0,N-1) if(bit[i][j]>=0 && !at[i][bit[i][j]]) at[i][bit[i][j]]=++cnt;
	VII ans(cnt+1);
	ans[0].PB(1);
	FOR(k,0,N-1){
		if(bit[0][k]<0) ans[0].PB(bit[0][k]^1);
		else ans[0].PB(at[0][bit[0][k]]);
	}
	FOR(i,0,d-1) FOR(j,0,sz[i]-1) if(at[i][j]){
		ans[at[i][j]].PB(i&1);
		FOR(k,0,N-1){
			if(bit[i][k]<0) ans[at[i][j]].PB(bit[i][k]^(i&1));
			else if(bit[i][k]!=j) ans[at[i][j]].PB((bit[i][k]<j?-1:-2)^(i&1));
			else if(bit[i+1][k]<0) ans[at[i][j]].PB(bit[i+1][k]^(i&1));
			else ans[at[i][j]].PB(at[i+1][bit[i+1][k]]);
		}
	}
	return ans;
}