|Source : ACM ICPC Central European Regional 1997|
|Time limit : 1 sec||Memory limit : 32 M|
Submitted : 135, Accepted : 64
Rewriting rules rewrite a letter at a position i, depending on letters at the positions i - 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps?
Help Dr. R. E. Wright and write a program which solves this task.
There are several blocks in the input, each describing one system. There is an integer number n, 2 < n < 16 the length of the input word in the first line. There is a word in the next line. The word contains only lowercase letters a and b. There are four characters c1 c2 c3 c4 in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i - 2 is c1 and the letter at the position i is c2 and the letter at the position i + 1 is c3 then the letter at the position i after rewriting will be c4. Rewriting rules are correct and complete. There is an integer number s, 0 <= s <= 2000000000, in the last line of the block.
There is one line corresponding to each block of the input. The line contains a word which we receive after s rewriting steps from the corresponding starting word using given rewriting rules. As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.
5 aaaaa aaab aabb abab abbb baab babb bbab bbbb 1