该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

同学们都非常熟悉汉诺塔问题：有三根柱子，分别用字母 A、B、C 表示。有 n 个圆盘，每个圆盘按大小编号 1,2,…,n (1 是最小的圆盘)，并且要求三根柱子上的圆盘都要满足 “大盘在下，小盘在上” 的条件。

你的任务是从一个给定初始状态出发，把所有圆盘移动到柱子 C，移动时需要遵循如下规则：

每次只能移动一个圆盘，每次移动的圆盘必须是某个柱子最上面的那个； 任意时刻都不能将大圆盘放在小圆盘上方。 请你找到步数最少的移动方案。

输入格式

输入第一行一个整数 n，表示圆盘数量。 第二行一个长度为 n 的字符串 S，其中第 i 个字符表示编号为 i 的圆盘当前所在柱子 (A、B 或 C)。

输出格式

若最少步数为 k，则输出 k 行，每行的输出格式为 “X -> Y” (不含引号)，代表把 X 柱子上的一个圆盘移到 Y 柱子。如果方案有多种，输出任意一种即可。

输入输出样例

2
BA

A -> C
B -> C

说明/提示

对于 40% 的数据，1≤n≤4。

对于 100% 的数据，1≤n≤15。