// Author          : Apostolos Syropoulos
// Program         : Iterative solution of the towers of hanoi problem
//                   using bitwise operators.
// Date            : November 26, 2000
//
import java.io.*;

public class hanoiG2
{
  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)
       {
           final double log2 = Math.log(2);

           for( int move = 1; move < (1 << height) ; move++) 
	   {
              int piece = (int)( Math.log( move ^ ( move - 1 )) / log2 )  + 1;
	      int from = ( move >> piece ) * ( piece % 2 == 0 ? 1 : -1 ) % 3;
              int to = ( from + (piece % 2 == 0 ? 1 : -1)) % 3;
              from = (from +3) % 3;
	      to = (to + 3) % 3;
              moveDisk( (char)(from+65), (char)(to+65));
           }
       }

       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");
       }

}