题目描述

​ 汉诺塔来源于印度传说的一个故事，传说上帝创造世界时做了三根金刚石柱子，在一根柱子上从上往下从小到大顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘，只能移动在最顶端的圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。

现在有n个圆盘从上往下从小到大叠在第一根柱子上，要把这些圆盘全部移动到第三根柱子要怎么移动呢？请找出需要步骤数最少的方案。

输入格式

输入两行。 第一行为1个正整数n，表示有多少个圆盘需要移动。 第二行为3个字符串，分别表示起始柱、过渡柱、目标柱的名称。

输出格式

分行输出，每行输出一个移动的步骤。并输出一共移动了多少次。

样例数据

【输入样例】

3
A B C

【输出样例】

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

【样例解释】

  每行最前的数字表示当前对第几个圆盘执行操作，如第一行表示将第1个圆盘从A柱移动到C柱。
  最后一行输出的数字为一共移动的次数。

数据规模与约定

$1\leq n \leq 15$

时间限制：$1 \text{s}$

空间限制：$64 \text{MB}$