P1366. 单词演化系统

题目描述

R. E. Wright博士的班级正在研究改进的L-系统(L-Systems)。让我们解释必要的细节：考虑由两字母字母表$\{a, b\}$构成的长度为$n$的循环单词。"循环"意味着我们可以通过循环移位写出单词的$n$种形式，其中单词的第一个和最后一个字母被视为相邻。

重写规则根据位置$i-2$、$i$和$i+1$的字母来重写位置$i$的字母。每一步我们都重写单词的所有字母。给定初始单词和一组重写规则后，自然的问题是：经过$s$次重写步骤后，单词会变成什么样子？

请帮助R. E. Wright博士编写程序解决这个问题。

输入格式

输入包含多个块，每个块描述一个系统：

1. 第一行：整数$n$表示单词长度 ($2 < n < 16$)
2. 第二行：初始单词（仅包含小写字母$a$和$b$)
3. 接下来8行：每行包含4个字符$c_1 c_2 c_3 c_4$，表示一条重写规则：
   • 当位置$i-2$的字母是$c_1$
   • 且位置$i$的字母是$c_2$
   • 且位置$i+1$的字母是$c_3$时
   • 重写后位置$i$的字母变为$c_4$
4. 最后一行：整数$s$表示重写步骤数 ($0 \leq s \leq 2,000,000,000$)

输出格式

对于每个输入块，输出一行：

• 经过$s$次重写后的单词
• 由于单词可以循环移位，输出字典序最小的形式（$a < b$）

样例输入

5
aaaaa
aaab
aabb
abab
abbb
baab
babb
bbab
bbbb
1

样例输出

bbbbb

题目来源

Central Europe 1997