Word

Dr. Wright's class is studying a modified L-system. Here are the details you need.

Consider words of length $n$ over the two-letter alphabet $\{a, b\}$. Each word is cyclic: it can be written in any of its $n$ cyclic-shift forms, and the first and last letters are treated as neighbours.

A rewriting rule replaces the letter at a position $i$ based on the letters at positions $i-2$, $i$, and $i+1$ (indices are taken cyclically). In one step, all letters of the word are rewritten simultaneously.

Given a starting word and a set of rewriting rules, determine how the word looks after $s$ rewriting steps.

The input contains several blocks, each describing one system.

• The first line holds an integer $n$ with $2 < n < 16$, the length of the word.
• The second line holds the starting word, made up only of the lowercase letters a and b.
• Each of the next eight lines holds four characters $c_1 c_2 c_3 c_4$ describing one rewriting rule: if the letter at position $i-2$ is $c_1$, the letter at position $i$ is $c_2$, and the letter at position $i+1$ is $c_3$, then after rewriting the letter at position $i$ becomes $c_4$. The eight rules are correct and complete (they cover every combination of $c_1 c_2 c_3$).
• The last line of the block holds an integer $s$ with $0 \le s \le 2000000000$.

Process blocks until the end of input.

For each block, print one line containing the word obtained after $s$ rewriting steps. Because the word is cyclic it can be written in any of its $n$ shifted forms; print the lexicographically smallest such form, assuming a < b.