题目描述

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏有 3 个塔座，在 A 座自下而上、由大到小按顺序放置了多个金盘，每个金盘都有唯一标号，最上面的标号是1，从上到下标号依次加1。游戏的目标：把 A 座上的金盘全部移到 B 座上，可以借助 C 座，每次只能移动一个盘子，并且在移动过程中始终保持大盘在下，小盘在上。输入盘子数量，要求在最少的移动步骤时，输出每次移动顺序。

输入

输入一行一个整数n, 1<=n<=64.

输出

输出多行，每行是移动每个盘的顺序。

样例输入

3

样例输出

1:A->C
2:A->B
1:C->B
3:A->C
1:B->A
2:B->C
1:A->C