Problem F
Linden Mayor System
Aristid is the mayor of a town called Linden. He and the townsfolk love fractals. One day, Aristid decides to genetically alter trees so that they have mathematically pleasing structures. It turns out that the people of Linden will support this idea only if the trees are sufficiently “tree-like.” So Aristid came up with the following system to generate realistic looking trees. Since he’s a little vain, he decided to call it the Linden Mayor System.
Start with a sequence of letters $S_0$. This is the seed that will be used to generate the rest of the tree. Next define some rules to model the branching behavior of the tree. A rule will have the form $x \rightarrow y$, indicating that the letter $x$ will be replaced with the sequence $y$. By applying these rules to $S_0$, the new sequence $S_1$ is created. These rules can be applied over and over to produce new sequences. In general, to create $S_{n+1}$ from $S_ n$, replace all the letters in sequence $S_ n$ according to the rules. Some letters may not have a rule associated with them. Such terminal letters are not replaced.
As an example, consider the starting sequence A with rules: A $\rightarrow $ AB and B $\rightarrow $ A. The first four iterations are as follows:
|
$S_0$: |
A |
Starting sequence. |
|
$S_1$: |
AB |
A is replaced with AB by rule A $\rightarrow $ AB. Note that rule B $\rightarrow $ A couldn’t be applied. |
|
$S_2$: |
ABA |
Again, A is replaced by AB but B is replaced with A (rule B $\rightarrow $ A). |
|
$S_3$: |
ABAAB |
Keep applying rule A $\rightarrow $ AB for A’s and rule B $\rightarrow $ A for B’s... |
|
$S_4$: |
ABAABABA |
This is the resulting sequence after four iterations. |
Input
The first line will contain two positive integers $n$ and $m$ where $0 \leq n \leq 26$ and $0 \leq m \leq 5$. Following this will be $n$ lines defining the rules for a Linden Mayor System. Each line is of the form: $x$ -> $y$, indicating that $x$ is replaced by $y$. $x$ is an uppercase letter from A to Z, and $y$ will contain between one and five uppercase letters from A to Z. The last line will contain the starting sequence $S_0$, which is non-empty and no longer than $30$ characters and will contain only uppercase letters from A to Z.
Output
Output the resulting sequence $S_ m$ which is produced after $m$ iterations.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 4 A -> AB B -> A A |
ABAABABA |
