题目背景

约 $19$ 世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根竖杆，最左边的杆上自上而下、由小到大顺序串着由 $64$ 个圆盘构成的“塔”。游戏的目的是将最左边杆上的圆盘全部移到中间的杆上，规则是一次只能移动一个盘，且不允许大盘放在小盘的上面。

这就是著名的汉诺塔问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以 $64$ 个盘的移动次数是：$2^{64}-1=18,446,744,073,709,551,615$。

这是一个天文数字，若每一微秒可能计算（并不输出）一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决圆盘数量较小情况时的汉诺塔问题，但很难用计算机解决 $64$ 个圆盘的汉诺塔。

题目描述

输入汉诺塔问题中圆盘的数量，输出实现最终效果的 最少 移动次序。

这里假定圆盘从小到大编号为 $1, 2,3, ...$。

输入格式

$1$ 行，依次是一个正整数 $n$ 和三个依次表示从左起三根竖杆编号的字符。数据间用一个空格隔开。

输出格式

输出要实现最终效果，最少移动方案的移动次序。每次移动占一行，类似 $\verb|3:a->b|$ 的形式（把编号为 $3$ 的盘子从 $\verb|a|$ 杆移至 $\verb|b|$ 杆）。

输入输出样例

2 a b c

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

说明/提示

👀️ 对于$100\%$ 的数据，$1 \leq n \leq 18$。