The Best Name for Your Baby

In the year 29XX, the government of a small country somewhere on Earth introduced a law restricting people's first names to traditional names of their culture, in order to preserve their cultural uniqueness. The country's linguists specify a set of rules once every year, and only names conforming to that year's rules are allowed. In addition, the law requires each person to use a name of a specific length, calculated from their birth date, because otherwise too many people would use the same very popular names. Ever since this law was enacted, a common task for the parents of a new baby is to find the name that comes first in alphabetical order among the legitimate names of the given length, because names earlier in alphabetical order bring various benefits in their culture.

Legitimate names are the strings consisting only of lowercase letters that can be obtained by repeatedly applying the rule set to the initial string "S", a string consisting of a single uppercase letter S.

Applying the rule set to a string means choosing one of the rules and applying it. Each rule has the form $A \to \alpha$, where $A$ is an uppercase letter and $\alpha$ is a string of lowercase and/or uppercase letters. Applying such a rule to a string replaces one occurrence of the letter $A$ with the string $\alpha$. That is, when the string has the form $\beta A \gamma$, where $\beta$ and $\gamma$ are arbitrary (possibly empty) strings of letters, applying the rule rewrites it into $\beta \alpha \gamma$. If there are two or more occurrences of $A$, an arbitrary one of them may be chosen for the replacement.

Below is an example set of rules.

1. $S \to aAB$
2. $A \to$ (empty)
3. $A \to Aa$
4. $B \to AbbA$

Applying rule (1) to "S" gives "aAB". Applying (2) to it yields "aB", as $A$ is replaced by the empty string. Then rule (4) turns it into "aAbbA". Applying (3) to the first occurrence of $A$ gives "aAabbA". Applying (2) to the $A$ at the end yields "aAabb". Finally, applying (2) again to the remaining $A$ gives "aabb". As no uppercase letter remains, "aabb" is a legitimate name. We denote this rewriting process as follows:

$S \xrightarrow{(1)} aAB \xrightarrow{(2)} aB \xrightarrow{(4)} aAbbA \xrightarrow{(3)} aAabbA \xrightarrow{(2)} aAabb \xrightarrow{(2)} aabb$

Linguists may sometimes define a ridiculous rule set such as the following.

1. $S \to sA$
2. $A \to aS$
3. $B \to b$

The only possible rewriting sequence with this rule set is

$S \xrightarrow{(1)} sA \xrightarrow{(2)} saS \xrightarrow{(1)} sasA \xrightarrow{(2)} \cdots$

which never terminates, so no legitimate names exist in this case. Also, rule (3) can never be used, since its left-hand side $B$ appears nowhere else.

It may happen that no rules are supplied for some uppercase letters appearing during rewriting. In the extreme case, even $S$ might have no rule, in which case there are of course no legitimate names.

Your job is to write a program that finds the name earliest in alphabetical order among the legitimate names of the given length conforming to the given set of rules.

The input is a sequence of datasets, followed by a line containing two zeros separated by a space, which represents the end of the input. Each dataset starts with a line containing two integers $n$ and $l$ separated by a space, where $n$ ($1 \le n \le 50$) is the number of rules and $l$ ($0 \le l \le 20$) is the required length of the name. After that line, $n$ lines follow, each representing a rule. Each such line starts with one of the uppercase letters A to Z, followed by the character "=" (instead of "$\to$"), and then the right-hand side of the rule, which is a string of letters A to Z and a to z. The length of that string does not exceed 10 and may be zero. No spaces appear in the lines representing the rules.

The output consists of lines showing the answer to each dataset, in the same order as the input. Each line is a string of lowercase letters a to z: the first legitimate name, in alphabetical order, conforming to the rules and having the length given in the corresponding dataset. When the given rule set has no conforming string of the given length, the corresponding output line shows a single hyphen, "-". No other characters are included in the output.