题目描述

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

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

1. 每次只能移动一个圆盘，每次移动的圆盘必须是某个柱子最上面的那个；

2. 任意时刻都不能将大圆盘放在小圆盘上方。

请你找到步数最少的移动方案。

输入格式

输入第一行一个整数 n，表示圆盘数量。

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

输出格式

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

样例数据

input

2
BA

output

A -> C
B -> C

数据范围

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