#include <fstream>
using namespace std;

int a[100],n,nr;
bool v[100],t[100],w[100];

ifstream f("damesah.in");
ofstream g("damesah.out");

void afisare()
{
    if (nr==0)
    {
        for (int i=1;i<=n;i++)
            g << a[i] << ' ';
        g << "\n";
    }
    nr ++;
}

void back(int k)
{
    if (k==(n+1))
        afisare();
    for (int i=1;i<=n;i++)
        if ((v[i]==0) && (w[i+k]==0) && (t[i-k+n]==0))
        {
            a[k]=i;
            v[i]=w[i+k]=t[i-k+n]=1;
            back(k+1);
            v[i]=w[i+k]=t[i-k+n]=0;
        }
}

int main()
{
    f >> n;
    back(1);
    g << nr;
}