#include <stdio.h>
#define DIAG 27
#define MAXN 14
int n;
char p[DIAG],s[DIAG],col[MAXN],next[MAXN+1];
int regc[MAXN];
FILE *fin;
FILE *fout;

int perm(int l,int ac){
  int i,x,aux;
  if(l==n){//avem o solutie generata
    if(ac<1){//scriem primele 3 solutii
      for(i=0;i<n;i++)
        fprintf(fout,"%d ",regc[i]+1);
      fprintf(fout,"\n");
    }
    return ac+1;
  }else{
    x=0;
    while(next[x]!=0){//parcurgem listele
      regc[l]=next[x]-1;
      if(col[regc[l]]==0&&p[regc[l]+l]==0&&s[n-l-1+regc[l]]==0){
        col[regc[l]]=1;//marcam coloana si diagonalele pe care se afla
        p[regc[l]+l]=1;
        s[n-l-1+regc[l]]=1;

        aux=next[x];
        next[x]=next[next[x]];//scoatem elementul din lista
        ac=perm(l+1,ac);//generam in continuare permutarile
        next[x]=aux;//readaugam elemntul in lista

        col[regc[l]]=0;//demarcam coloana si diagonalele pe care se afla
        p[regc[l]+l]=0;
        s[n-l-1+regc[l]]=0;
      }
      x=next[x];//trecem la urmatorul element din lista
    }
  }
  return ac;
}

int main(){
  int i;
  fin=fopen("damesah.in","r");
  fout=fopen("damesah.out","w");

  fscanf(fin,"%d",&n);
  for(i=0;i<n;i++)//generam listele initiale
    next[i]=i+1;
  fprintf(fout,"%d",perm(0,0));
  fclose(fin);
  fclose(fout);
  return 0;
}