#include
int D[20],pred[20],succ[20],Nb=1,head,tail,m;
/******************************************/
rem_ove(int r)
{ if( r==head )
  head=succ[r];
  else { if( r==tail )
         tail=pred[tail];
	 else { succ[pred[r]]=succ[r];
	        pred[succ[r]]=pred[r];
              }
	}		
} /******************************************/
append(int r)
{ if( rtail )
         tail=r;
	 else { succ[pred[r]]=r;
                pred[succ[r]]=r;
	      }
       }
}/******************************************/
type()
{ int i; 
  printf("%d\t",Nb++);
  for (i=1;i<=m;i++) printf("%d",D[i]);
  printf("%c",'\n');
}/******************************************/

init()
{ int i;
  printf("donnez :"); scanf("%d",&m);
  head=1;tail=m+1;
  for (i=1;i< (m+1);i++)  succ[i]=i+1;
  for (i=2;i<=(m+1);i++) pred[i]=i-1;
  for (i=1;i< m;i++) D[i]=i+1 ; D[m]=1;
  type();
}/******************************************/

transp(int a, int b)
{ int aux;
  aux=D[a];
  D[a]=D[b];
  D[b]=aux;
}/******************************************/ 
left (int a, int b, int c)
{ transp(a,b); transp(b,c); }/**************/ 
right(int a, int b, int c)
{ transp(b,c); transp(a,b);}/**************/ 

psi_up(int r)
{ if (r==head)
  { transp(head,succ[head]);
    transp(pred[tail],tail);}
  else
  { transp(pred[r],tail);
    transp(r,succ[r]);
  }
type();
}/******************************************/ 

psi_dw(int r)
{ if (pred[r]==head)
  { transp(head,succ[head]);
    transp(pred[tail],tail);}
  else
  { transp(pred[pred[r]],tail);
    transp(pred[r],r);
  }
type();  
}/******************************************/ 
phi_up(int r)
{ right(pred[r],r,tail);type();}/*****/

phi_dw(int r)
{ left(pred[pred[r]],pred[r],tail);type();}/*******/

phi_psi(int r,int i,int n)
{ if (n==4)
  { if (i==3) transp(head,pred[tail]); else transp(r,succ[r]);}
else 
{ if (i==1)
  { if ((n%2)==0) 
    right(head, pred[pred[pred[tail]]], pred[pred[tail]]);
    else left(head, pred[pred[pred[tail]]], pred[pred[tail]]);
  } 
  else if ( (i>=2) && (i<= (n-4)) )
  { transp(pred[r],r);  transp(pred[pred[pred[tail]]],pred[pred[tail]]);
  }
  else if ( i== (n-3) )
  right (pred[pred[pred[pred[tail]]]],pred[pred[pred[tail]]],pred[pred[tail]]);
  else if ( i== (n-2) )
  left (pred[pred[pred[pred[ tail ]]]],pred[pred[tail]],pred[tail]);
  else if ( i== (n-1) )
  { if ((n%2)==0) 
    { transp(pred[pred[pred[pred[ tail ]]]] , pred[pred[ tail ]]); 
      transp(pred[pred[pred[ tail ]]] , pred[tail] );}
    else right(pred[pred[pred[pred[ tail ]]]], pred[pred[ tail ]] , pred[tail] );
  }
}type();
}/******************************************/ 


psi_phi(int r,int i,int n)
{ if (n==4)
  { if (i==3) transp(head,pred[tail]); else transp(r,succ[r]);}
else 
{ if (i==1)
  { if ((n%2)==0) 
    left(head, pred[pred[pred[tail]]], pred[pred[tail]]);
    else right(head, pred[pred[pred[tail]]], pred[pred[tail]]);
  } 
  else if ( (i>=2) && (i<= (n-4)) )
  { transp(pred[r],r);  transp(pred[pred[pred[tail]]],pred[pred[tail]]);
  }
  else if ( i== (n-3) )
  left (pred[pred[pred[pred[tail]]]],pred[pred[pred[tail]]],pred[pred[tail]]);
  else if ( i== (n-2) )
  right (pred[pred[pred[ pred[tail ]]]],pred[pred[tail]],pred[tail]);
  else if ( i== (n-1) )
  { if ((n%2)==0) 
    { transp(pred[pred[pred[pred[ tail ]]]] , pred[pred[ tail ]]); 
      transp(pred[pred[pred[ tail ]]] , pred[tail ]);}
    else left(pred[pred[pred[pred[ tail ]]]] , pred[pred[ tail ]] , pred[tail]);
  }
}type();
}/******************************************/ 

gen_up(int n,int t, int r)
{ int i,run;
  tail=pred[tail];
  if (t==1) rem_ove(r);
  if (n==3) {left(head,succ[head],tail);  type(); }
  else 
  { run=head;
     for (i=1;i<=n-1;i++)
     {  if ( (i%2) ==1)  
        {  gen_up(n-1,0,run);
	   phi_psi(run,i,n);
	   if (n>4) gen_dw(n-2,1,run);
	   if (i != (n-1) )
	   { psi_up(run);
             run=succ[run];
	   }  
 	}
	else
	{  if (n>4) gen_up(n-2,1,run);
	   psi_phi(run,i,n);
	   gen_dw(n-1,0,run);
	   if (i != (n-1) )
	   { phi_up(run);
             run=succ[run];
	   }  
	}
     }
  }
  if (t==1) append(r);  
  tail=succ[tail];        
}/******************************************/ 
gen_dw(int n,int t, int r)
{ int i,run;
  tail=pred[tail];
  if (t==1) rem_ove(r);
  if (n==3) { right(head,succ[head],tail); type();}  
  else 
  {  run=pred[tail]; 
     for (i=n-1;i>=1;i--)
     {  if ( (i%2) ==1)  
        { if (n>4) gen_up(n-2,1,run);
	  psi_phi(run,i,n); 
	  gen_dw(n-1,0,run);
     	  if (i != 1 )
	  { phi_dw(run);
            run=pred[run];
	  }
	}  
        else
	{ gen_up(n-1,0,run);
	  phi_psi(run,i,n);
	  if (n>4) gen_dw(n-2,1,run);	  
	  psi_dw(run);
	  run=pred[run];
	}
     }
  }
  if (t==1) append(r);
  tail=succ[tail];  
}/******************************************/   
   

main()
{ init();
  if(m>=3)gen_up(m,0,0); 
}