#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

const int N=5010,M=30;
int dp[N],pre[N],mk[M];
vector< pair<int,int> > v[M],w[M];
vector< vector<int> > devise_strategy (int n) {
	vector< vector<int> > ans;
	dp[1]=dp[2]=0;
	for (int i=3;i<=n;i++) {
		dp[i]=1e9;
		for (int j=1;j<=20;j++) {
			if (dp[(i+j-3)/j]+j<=dp[i]) {pre[i]=j,dp[i]=dp[(i+j-3)/j]+j;} 
		}
	}
	v[0].push_back(make_pair(1,n));
	w[0].push_back(make_pair(1,n));
	int cur=0,tot=0,fk=0;
	for (int i=0;i<=tot;i++) {
		if (i==0||(mk[i]^mk[i-1])) {
			cur=tot;
			int le=0;
			for (int k=i;k<=tot;k++) {
				int len=v[k].size();
				for (int j=0;j<len;j++) {le=max(le,v[i][j].second-v[i][j].first+1);}
			}
			if (pre[le]) {
				fk=(le+pre[le]-3)/pre[le];
				while (tot<cur+(le+fk-3)/fk) {tot++;mk[tot]=(mk[i]^1);}
			} else {fk=0;}
		}
		vector <int> tmp(n+1);
		tmp[0]=mk[i];
		int len=v[i].size();
		for (int j=0;j<len;j++) {
			//printf("%d  %d    %d  %d\n",i,j,v[i][j].first,v[i][j].second);
			int nle=v[i][j].second-v[i][j].first+1;
			if (fk) {
				for (int k=1;k<=(nle+fk-3)/fk;k++) {
					v[cur+k].push_back(make_pair(v[i][j].first+1+(k-1)*fk,v[i][j].first+min(nle-2,k*fk)));
					w[cur+k].push_back(v[i][j]);
				}
			}
			for (int k=1;k<=n;k++) {
				if (k>=w[i][j].first&&k<=w[i][j].second) {
					if (k<=v[i][j].first) {tmp[k]=(mk[i]?-2:-1);}
					else if (k>=v[i][j].second) {tmp[k]=(mk[i]?-1:-2);}
					else {tmp[k]=cur+(k-v[i][j].first-1)/fk+1;}
				}
			}
		}
		ans.push_back(tmp);
	}
	//printf("%d  %d\n",tot,dp[n]);
	//for (int i=0;i<=tot;i++) {printf("%d",mk[i]);
		//for (int j=0;j<=n;j++) {
		//	printf("%-5d  ",ans[i][j]);
		//}
		//printf("\n");
	//}
	return ans;
}