// Author   : Apostolos Syropoulos
// Program  : French Solution of the Towers of Hanoi puzzle
// Date     : December 31, 1997
//
import java.io.*;

public class hanoiD
{
       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,
                         char  fromPole,
                         char  toPole,
                         char  withPole)
       {
          int MaxMoves = (int)Math.pow(2, height)-1;
          int[] S = new int[MaxMoves+1];
          int i, j, middle;
          boolean current_even, previous_even;
          char temp;

          S[0] = 0; S[1] = 1;
          for (i=2; i <= height; i++)
          {
             middle = (int)Math.pow(2, i-1);
             S[middle] = i;
             for (j=middle+1; j <= 2*middle-1; j++)
             {
                S[j] = S[j-middle];
             }
          }
          previous_even = ((height % 2) == 0)? true : false; 
          for (i=1; i <= MaxMoves; i++)
	  {
	     current_even = ((S[i] % 2) == 0) ? true : false;
             if (current_even)
	     { 
	        temp = toPole; // swap(toPole, withPole)
                toPole = withPole;
                withPole = temp;
	     }            
             else if (!current_even && previous_even)
	     {
	        temp = fromPole; // swap(fromPole, withPole)
                fromPole = withPole;
                withPole = temp;
	     }
             else if (!current_even && !previous_even)
	     {
	        temp = fromPole; // swap(fromPole, withPole);
                fromPole = withPole;
                withPole = temp;

                temp = toPole; //swap(toPole, withPole)
                toPole = withPole;
                withPole = temp;
             }
             moveDisk(fromPole, toPole);
             previous_even = current_even;
	  }
       }

       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;
            char FromPole='B', ToPole='C', WithPole='A';

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