题目描述

在一个列车调度站中，$\red {2}$ 条轨道连接到$\red {2}$条侧轨处，形成$\red {2}$ 个铁路转轨栈。其中左边轨道为车皮入口，编号为$\red {A}$；右边轨道为出口，编号为$\red {D，2}$ 个铁路转轨栈分别编号为$\red {C}$和$\red {D}$，如下图所示。编号为$\red {a，b，…}$，的$\red {n}$ 个车皮依序停放在车皮入口处。调度室要安排各车皮进出栈次序，使得在出口处各车皮按照预先指定的顺序依次出站。车皮移动时只能按照从左到右的方向移动。

给定车皮数$\red {n}$，以及各车皮的出站顺序，编程计算最优调度方案，使得移动车皮的总次数最少。

输入格式

第一行有$\red {1}$ 个正整数$\red {n}$，表示车皮数。接下来的$\red {1}$ 行中，是预先指定的车皮出站顺序。

输出格式

文件的第一行是最少移动次数$\red {m}$。接下来的$\red {m}$行是对应于最优方案的$\red {m}$次移动。每次移动用形如$\red {‘C X Y’}$的$\red {3}$ 个字符来表示，其中$\red {C}$ 表示车皮编号，$\red {X}$表示起始栈轨号，$\red {Y}$ 表示目标栈轨号。如果无法调度则输出“No Solution!”。

样例

输入样例

3

abc

输出样例

5

c A B

b A B

a A D

b B D

c B D