// Author   : Apostolos Syropoulos
// Program  : ``Fourth Grade Solution'' Towers of hanoi
// Date     : November 16, 1997
//
import java.io.*;
import java.lang.Math;

public class hanoiC
{
  static int moves=0; //number of moves so far

       static int getInt()
       {
           String line;
           BufferedReader in = 
           new BufferedReader(new InputStreamReader(System.in)); 
           try
           {
              line = in.readLine();
              int i = Integer.valueOf(line).intValue();
              return i;
           }
           catch (Exception e)
           {
              System.err.println("***Error: Input is not a number.\n" +
                                 "Input assumed to be the number 1");
              return 1;
           }
       }

       static void hanoi(int height)
       {
           int fromPole, toPole, Disk;
           int[]   BitStr = new int[height],
                   Hold   = new int[height];
           char[]  Place  = {'A', 'C', 'B'};
           int i, j, temp;
 
           for (i=0; i<height; i++)
	   {
              BitStr[i] = 0;
              Hold[i] = 1;
           }
           temp = 3 - (height % 2);
           int TotalMoves = (int) Math.pow(2, height) - 1;
           for (i=1; i <= TotalMoves; i++)
	   {
              for (j=0 ; BitStr[j] != 0; j++)
                  BitStr[j] = 0;
              BitStr[j] = 1;
              Disk = j+1;
              if (Disk == 1)
	      {
                 fromPole = Hold[0];
                 toPole = 6 - fromPole - temp;
                 temp = fromPole;
	      }
              else
	      {
                 fromPole = Hold[Disk-1];
                 toPole = 6 - Hold[0] - Hold[Disk-1];
	      }        
              moveDisk(Place[fromPole-1], Place[toPole-1]);
              Hold[Disk-1] = toPole;
	   }
       }

       static void moveDisk(char fromPole, char toPole)
       {
            moves++;
            System.out.print(fromPole);
            System.out.print(toPole);
            System.out.print(((moves % 20)==0) ? '\n' : ' ');
       }

       public static void main(String[] args)
       {
            long time1, time2; //for benchmarking
            int TowerHeight;

            System.out.println("Enter Tower height...");
            System.out.print("?");
            TowerHeight = getInt();
            time1 = System.currentTimeMillis();
            hanoi(TowerHeight);
            time2 = System.currentTimeMillis();
            System.out.println();
            System.out.print(time2-time1); //print execution time in msec
            System.out.println(" msec execution time");
       }

}