24784번 - 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:

입력

The first line will contain two positive integers: 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$ and $y$ will contain only uppercase letters from A to Z, and the length of $y$ is guaranteed to be at most five. The last line will contain the starting sequence $S_0$ which will be no longer than 30ドル$ characters and will contain only uppercase letters from A to Z.

출력

Output the resulting sequence $S_m$ which is produced after $m$ iterations.

제한

힌트