using Nemerle.Collections;
using Nemerle.IO;

module Hanoi {
  mutable stacks : array [list [int]];

  print_stacks () : void
  {
    def loop (max, i) {
      if (i >= stacks.Length) max
      else {
        def len = List.Length (stacks[i]);
        loop (if (len > max) len else max, i + 1)
      }
    };
    def maxval = loop (0, 0);
    
    for (mutable i = 0; i < maxval; i++) {
      for (mutable j = 0; j < stacks.Length; j++) {
        def off = maxval - List.Length (stacks[j]);
        if (i <= off - 1)
          printf (" |")
        else
          printf (" %d", List.Nth (stacks[j], i - off))
      };
      printf ("\n");
    };
    
    printf ("\n");
  }

  move (a : int, b : int) : void
  {
    match (stacks[a]) {
      | head :: tail =>
        stacks[a] = tail;
        stacks[b] = head :: stacks[b];
        print_stacks ()
      | [] => assert (false)
    }
  }

  solve (n : int, a : int, b : int, c : int) : void
  {
    when (n > 0) {
      solve (n - 1, a, c, b);
      move (a, b);
      solve (n - 1, c, b, a);
    }
  }
  
  Main () : void 
  {
    mutable height = 0;
    scanf ("%d", height);
    def loop (n) { if (n == 0) [] else n :: loop (n - 1) };
    stacks = array [List.Rev (loop (height)), [], []];
    print_stacks ();
    solve (height, 0, 2, 1)
  }
}

/*
BEGIN-INPUT
3
END-INPUT
BEGIN-OUTPUT
 1 | |
 2 | |
 3 | |

 2 | |
 3 | 1

 3 2 1

 | 1 |
 3 2 |

 | 1 |
 | 2 3

 1 2 3

 | | 2
 1 | 3

 | | 1
 | | 2
 | | 3

END-OUTPUT
*/