题目描述

汉诺塔（Tower of Hanoi）是一个经典的递归问题。现由于某种神秘力量，我们拥有三根固定的杆子，分别命名为 a、b 和 c。

游戏规则如下：

1. 初始时，所有的 $n$ 个盘子都叠放在杆子 a 上，从上到下尺寸依次递增。
2. 每次只能移动一个盘子。
3. 在移动过程中，大盘子永远不能放在小盘子上面。
4. 最终目标是将所有盘子从杆子 a 移动到杆子 c（可借助杆子 b）。

请输出实现这一目标的所有移动步骤。

输入格式

输入一个正整数 $n$，表示起始杆 a 上的盘子数量。

输出格式

输出若干行，每行记录一次移动。 格式为：源杆子编号->盘子编号->目标杆子编号 （例如 a->1->c 表示将 1 号盘子从 a 移动到 c）。

输入输出样例

输入 #1

2

输出 #1

a->1->b
a->2->c
b->1->c

数据范围

• 对于 $100\%$ 的数据，$1 \le n \le 15$。