#include <bits/stdc++.h>
#define nmax 50
using namespace std;
string prob="damesah";
ifstream in(prob+".in");
ofstream out(prob+".out");
bool col[nmax],d1[nmax],d2[nmax*nmax];
vector<int> rez;
int sol=0;
int n;
void b(int l){
    if(l>n){
        if(!sol){
            for(auto i:rez)out<<i<<' ';
            out<<'\n';
        }
        sol++;
    }
    for(int i=1;i<=n;i++){
        if(!(col[i]||d1[l+i-2]||d2[l-i+nmax])){
            col[i]=d1[l+i-2]=d2[l-i+nmax]=1;
            rez.push_back(i);
            b(l+1);
            col[i]=d1[l+i-2]=d2[l-i+nmax]=0;
            rez.pop_back();
        }
    }
}
int main(){
    in>>n;
    b(1);
    out<<sol;
}