#include<cstdio>
const int M=20000000;
int n,m,q[14],c[14],a[28],b[28],l,o;
char r[M];
inline void S(int x)
{
    int i,d=x>999999999?10:x>99999999?9:x>9999999?8:x>999999?7:x>99999?6:x>9999?5:x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,i--)
        r[o+i]=x%10+48;
    r[o+d]=10,o+=d+1;
}
void A(int l)
{
	int i;
    if(l==n)
	{
        if(m<1)
		{
            for(i=0;i<n;i++)
                if(q[i]>8)
                    r[o++]=49,r[o++]=q[i]+39,r[o++]=32;
                else
                    r[o++]=q[i]+49,r[o++]=32;
            r[o++]=10;
        }
        m++;
    }
    else
        for(i=0;i<n;i++)
        	if(!c[i]&&!a[i-l+n-1]&&!b[l+i])
            	q[l]=i,c[i]=a[i-l+n-1]=b[l+i]=1,A(l+1),c[i]=a[i-l+n-1]=b[l+i]=0;
}
int main()
{
	freopen("damesah.in","r",stdin),freopen("damesah.out","w",stdout),scanf("%d",&n),A(0),S(m),fwrite(r,1,o,stdout);
}