#include<vector>
#define pr pair<int,int>
#define vi vector<int>
using namespace std;
int n;vector<vi>ans;vector<pr>a[33];
inline vi make(const int&x){return vi(1,x);}
inline vi make(const int&x,const int&y)
{vector<int>o;o.emplace_back(x);o.emplace_back(y);return o;}
inline bool ok(const int&i,const int&l,const int&r)
{
for(int j=0;j<a[i].size();++j)
{
if(a[i][j].first<=l&&l<=a[i][j].second)return 0;
if(a[i][j].first<=r&&r<=a[i][j].second)return 0;
if(l<=a[i][j].first&&a[i][j].first<=r)return 0;
if(l<=a[i][j].second&&a[i][j].second<=r)return 0;
}
return 1;
}
inline void work(const int&i,const int&l,const int&r,const vi&u,
const vi&v,const vi&w)
{
for(int j=0;j<u.size();++j)for(int k=u[j];k<=v[j];ans[i][k++]=w[j]);
if(l>=r)return;
int o=ans[i][0],mid=l+r>>1,j;
ans[i][l]=-o-1;ans[i][r]=-(o^1)-1;
if(r-l==1)return;//边界
if(r-l==2)//边界
{
for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))
{
a[j].emplace_back(l,r);ans[i][mid]=j;
work(j,l+1,r-1,make(l,r),make(l,r),make(-(o^1)-1,-o-1));
return;
}
ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
j=ans[i][mid]=ans.size()-1;a[j].emplace_back(l,r);
work(j,l+1,r-1,make(l,r),make(l,r),make(-(o^1)-1,-o-1));
return;
}
if(r-l>=6)//分三半
{
int m1=l+(r-l-1.)/3+0.5,m2=r-(r-l-1.)/3+0.5;
for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//左
{
a[j].emplace_back(l,r);
for(int k=l+1;k<=m1;ans[i][k++]=j);
work(j,l+1,m1,make(l,m1+1),make(l,r),make(-(o^1)-1,-o-1));
goto qaq;
}
ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
j=ans.size()-1;a[j].emplace_back(l,r);
for(int k=l+1;k<=m1;ans[i][k++]=j);
work(j,l+1,m1,make(l,m1+1),make(l,r),make(-(o^1)-1,-o-1));
qaq:;
for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//中
{
a[j].emplace_back(l,r);
for(int k=m1+1;k<m2;ans[i][k++]=j);
work(j,m1+1,m2-1,make(l,m2),make(m1,r),make(-(o^1)-1,-o-1));
goto quq;
}
ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
j=ans.size()-1;a[j].emplace_back(l,r);
for(int k=m1+1;k<m2;ans[i][k++]=j);
work(j,m1+1,m2-1,make(l,m2),make(m1,r),make(-(o^1)-1,-o-1));
quq:;
for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//右
{
a[j].emplace_back(l,r);
for(int k=m2;k<r;ans[i][k++]=j);
work(j,m2,r-1,make(l,r),make(m2-1,r),make(-(o^1)-1,-o-1));
return;
}
ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
j=ans.size()-1;a[j].emplace_back(l,r);
for(int k=m2;k<r;ans[i][k++]=j);
work(j,m2,r-1,make(l,r),make(m2-1,r),make(-(o^1)-1,-o-1));
return;
}
for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//左半边
{
a[j].emplace_back(l,r);
for(int k=l+1;k<=mid;ans[i][k++]=j);
work(j,l+1,mid,make(l,mid+1),make(l,r),make(-(o^1)-1,-o-1));
goto qwq;
}
ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
j=ans.size()-1;a[j].emplace_back(l,r);
for(int k=l+1;k<=mid;ans[i][k++]=j);
work(j,l+1,mid,make(l,mid+1),make(l,r),make(-(o^1)-1,-o-1));
qwq:;
for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//右半边
{
a[j].emplace_back(l,r);
for(int k=mid+1;k<r;ans[i][k++]=j);
work(j,mid+1,r-1,make(l,r),make(mid,r),make(-(o^1)-1,-o-1));
return;
}
ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
j=ans.size()-1;a[j].emplace_back(l,r);
for(int k=mid+1;k<r;ans[i][k++]=j);
work(j,mid+1,r-1,make(l,r),make(mid,r),make(-(o^1)-1,-o-1));
}
vector<vi>devise_strategy(int N)
{
n=N;ans.emplace_back(vi(n+1));ans[0][0]=0;
work(0,1,n,vi(),vi(),vi());
return ans;
}
