填空题

核子聚变

Question

请设计一个程序，在规定步数内，成功的使得一个原子核队列完全湮灭。

7种原子核(用A-G表示)，排成一条直线队列，在初始状态下它们是稳定的。

如果我们发射一个额外的原子核插入到队列，如果插入的位置没有形成大于等于3个相同的原子核的序列，那么队列继续保持稳定。

如果该位置上相邻的三个或以上的原子核种类相同， 就会诱发聚变湮灭成能量散失；然后队列上剩下的左右两半会受外部压力重新拼接在一起，拼接点两侧如果类型相同，且拼接后形成三个或以上连续相同序列，则连锁反映继续聚变湮灭。

为了方便描述插入位置，假定队列长度为n，我们把对列最左端外侧位置编号为0，右端外侧位置编号为n，共有n+1个位置。

例如：

AAABC，如果把一个A插入到位置4（或位置5）的时候，队列会变成AAABAC，继续稳定存在。

AABBCCA，如果把一个C插入到位置4（或位置5,6）的时候，会形成3个C，之后3个C会湮灭，队列变成AABBA，重新恢复稳定。

BAABBCCBACCB，一个C色球插入到位置5（或位置6,7）的时候，会触发连锁反应消去的过程如下（"+"表示拼接点）：

  BAABB+C+CCBACCCB => BAABB+BACCCB => BAA+ACCCB => B+CCCB => BCCCB (稳定)

  注意最后剩下3个连续的C，是因为最后一步拼接时，拼接点左右类型并不相同，不会触发连锁反应。

每在队列中新插入一个原子核，记为一步；每一步可插入任意类型的原子核。

本题给出1）初始的队列，2）要求在几步之内达成完全湮灭。

要求选手给出一个消去过程，将所有的原子核都聚变湮灭。该过程必须在给定的步数上限之内完成才算正确。

请选手注意，本题并不要求最优解，只需要给出一个不超过步数上限的解即可。

输入描述： 共两行，第1行是一行字母(长度<=200)，表示初始原子核的序列，不同的字母表示不同的类型，第2行是一个十进制整数（<=100），表示要求选手在多少步完成全部湮灭。

本题45%的case，初始字符串长度不大于30。

例如：

AAABBAAACCABDCAABC

10输入样例： AAABBAAACCABCAABC 10 输出描述： 若干行，每一行是一步，包含一个字母和一个数字，用空格分开；分别表示为这一步要插入的原子核类型，以及插入的位置。0表示最左端，n表示第n个字母的右侧。
例如对于上述的例子输入的的合法输出可以是：

C 8
C 3
C 3
D 5
D 5
B 0
B 0
C 0
C 0
这个输出文件共9行，小于输入文件的步数限制10，因此这个消去过程成立，该case通过。

注意：合法输出不唯一，也不要求最优解。

下面具体解释上述消去序列的每一步的输出和变化如下
C 8 ：AAABBAAACCCABDDAA => AAABBAAA+ABDCAABC => AAABB+BDCAABC => AAADDAA
C 3 ：AAACDCAABC
C 3 ：AAACCDCAABC
D 5 ：AAACCDDCAABC
D 5 ：AAACCDDDCAABC => AAACC+CAABC => AAA+AABC => BC
B 0 ：BBC
B 0 ：BBBC => C
C 0 ：CC
C 0 ：CCC => empty输出样例 C 8 C 3 C 3 B 0 B 0 C 0 C 0