题目描述

汉诺塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子从下网上按照大小顺序摞着64篇黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。当把64片圆盘从第一根石柱移动到第三根石柱时，这个世界就会毁灭。

而婆罗门移动圆盘需要用多少时间呢？通过平常的方法是很难计算的。

请用递归思想来计算一下汉诺塔移动次数和移动步骤。

输入格式

输入为一个整数(小于20）后面跟三个单字符字符串。整数为盘子的数目，后三个字符表示三个杆子的编号。

输出格式

输出每一步移动盘子的记录。一次移动一行。每次移动的记录为例如 A->C 的形式，即将A上的盘子移动到C盘。

样例

3

A->C
A->B
C->B
A->C
B->A
B->C
A->C

Limitation

1s, 1024KiB for each test case.