圆盘移动问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

从左向右依次安放4根细柱A,B,C,D。在A柱上套有n(n<=20)个直径相同的圆盘,从下到上依次用连续的小写字母a,b,c,……编号: 


将这些圆盘经过B,C单向地移动到D柱上(即不允许从右向左移动。圆盘可在B,C中暂存)。

要求找到从A柱初始状态到D柱目标状态的移动过程。

Input

输入有两行:第一行是D柱上的圆盘总数,第二行是D柱上由下到上的圆盘的序列。

Output

每一行为形如“k m l”的字母序列,其中k为圆盘编号,m为k盘原先的柱号,l为目标柱号。如果不能生成排列,则输出 “no solution!”

Sample Input

3
abc

Sample Output

c A B
b A C
a A D
b C D
c B D

Hint

Source