import Prog1Tools.IOTools;
public class ADE{  
 //
 //
 // Die folgende Prozedur bewirkt den Test auf "Nicht-Achlagen"
 // von allen Permutationen der Art 
 // brett[0], brett[1], brett[2],..., brett[d-1] fest bleibend, 
 // gefolgt von allen Permutationen 
 // von brett[d], brett[d+1],..., brett[x.length-1]. 
 // Dabei ist d >= x.length. Bei d == x.length 
 // haben wir dann nur noch eine Permuation.  
 // Und der Test wird ausgefuehrt. 
 //
 //
 static int z= 1;
 //
 public static void Erz(int[ ] brett, int d){     
     if (d == brett.length )  // Nicht  d == brett.length - 1!!
     if (Test(brett) == false) {System.out.print( z + ".  ");
				   Ausgabe(brett);
                                 z++;}
       
     
     //
     //
     int i = d, b;  // Hier ist d <= brett.length - 1!
     //
     //
     while  (i < brett.length) {
     //
     b = brett[i];     // brett[d] und brett[i] vertauschen.
     brett[i] = brett[d];
     brett[d] = b;
     //
     Erz(brett, d+1);
     //
     b = brett[i];    // brett[i] und brett[d] (zurueck-)vertauschen. 
     brett[i] = brett[d];
     brett[d] = b;
     //
     //
     //
     i++;
     }   
        }
 //
 //
 //
 public static void Ausgabe(int[  ] brett) {
 int i = 0;
 while (i < brett.length) {
    System.out.print(" " + brett[i]);
    i++; 
    }
 System.out.println( );     
 }     
  //
  //
  public static boolean Test(int[] brett) {
  //
  int spalte = 0;
  //
  for (spalte = 0; spalte < brett.length; spalte++) {  
          // Test nach links oben.
     for (int i = spalte-1, j = brett[spalte] -1; i >= 0; i--, j--) {
         if (brett[i] == j) return true;
	 }
  
         // Test nach links unten.
     for (int i = spalte-1, j = brett[spalte] +1; i >= 0; i--, j++) {
         if (brett[i] == j) return true;
	 }
  }
  return false;
  }
  //
  //
  //
  // Die Deklarationen  enden.
  //
  //
  //
  public static void main(String[] args) {
  //
  int n, i= 0;
  int[ ] brett;
  //
  //  
  //
  n = IOTools.readInteger("n einlesen " );
  brett = new int[n];
  //
  while (i< brett.length){
  brett[i] = i;
  i++; }
  //
  // Initialisierung der lokalen Variablen beendet. 
  //
  //
  //
  Erz(brett, 0);
  //
  //
   }
  }