// Author   : Apostolos Syropoulos apostolo@obelix.ee.duth.gr
// Program  : Non recursive solution to the towers of hanoi puzzle
// Date     : June 13, 1999
//
import java.io.*;
import java.math.*;

public class hanoiF
{
  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)
       {
           BigInteger  ba, ac, cb, ab, bc, ca, m;
           int n;
           
           ba = new BigInteger("0");
           ac = new BigInteger("0");
           cb = new BigInteger("0");
           ab = new BigInteger("0");
           bc = new BigInteger("0");
           ca = new BigInteger("0");

	   if ( height % 2 != 0 ) // N is odd 
           {
              n  = height-1;
              ba = new BigInteger("4");
              ac = new BigInteger("5");
              cb = new BigInteger("0");
              m  = new BigInteger("6");
           }
           else    /* N is even */
           {
              n  = height-2;
              ba = new BigInteger("134");
              ac = new BigInteger("69");
              cb = new BigInteger("73");
              m  = new BigInteger("216");
           }

          while ( n > 2 )
         {
              n--;
              ba = cb.add(m.multiply(
                   new BigInteger("1").add(ac.multiply(
                   new BigInteger("6")))));
              ca = ba.add(m.multiply(
                   new BigInteger("2").add(cb.multiply(
                   new BigInteger("6")))));
              bc = ac.add(m.multiply(
                   new BigInteger("3").add(
                   ba.multiply(new BigInteger("6")))));
              m  = new BigInteger("6").multiply(m.multiply(m));
              n--;
              ba = ca.add(m.multiply(
                   new BigInteger("4").add(bc.multiply(
                   new BigInteger("6")))));
              ac = bc.add(m.multiply(
                   new BigInteger("5").add(ab.multiply(
                   new BigInteger("6")))));
              cb = ab.add(m.multiply(ca.multiply(new BigInteger("6"))));
              m  = new BigInteger("6").multiply(m.multiply(m));
         }

         if ( n == 2 )
         {
            n--;
            ab = cb.add(m.multiply(
                 new BigInteger("1").add(ac.multiply(
                 new BigInteger("6")))));
            bc = ac.add(m.multiply(
                 new BigInteger("3").add(ba.multiply(
                 new BigInteger("6")))));
            m  = new BigInteger("6").multiply(m.multiply(m));
         }
         if ( n == 1 )
         {
            ac = bc.add(m.multiply(
                 new BigInteger("5").add(ab.multiply(
                 new BigInteger("6")))));
         }

        int k=0, total_moves=((int)Math.pow(2,height))-1;
        String[] moves  = new String[total_moves];
        BigInteger[] dAR;
        BigInteger r;
 
        while (ac.compareTo(new BigInteger("0")) != 0)
        {
            dAR = ac.divideAndRemainder(new BigInteger("6"));
            ac = dAR[0];
            r  = dAR[1];

            if(r.compareTo(new BigInteger("0")) == 0)
                moves[k] = "CB ";
            else if(r.compareTo(new BigInteger("1")) == 0)
                moves[k] = "AB ";
            else if(r.compareTo(new BigInteger("2")) == 0)
                moves[k] = "CA ";
            else if(r.compareTo(new BigInteger("3")) == 0)
                moves[k] = "BC ";
            else if(r.compareTo(new BigInteger("4")) == 0)
                moves[k] = "BA ";
            else if(r.compareTo(new BigInteger("5")) == 0)
                moves[k] = "AC ";
            k++; 
        }
     
       for (int i=k-1; i>=0; i--)
       {
          System.out.print(moves[i]);
       } 
    }      

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

}