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

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

Applying the rule set to a string is to choose one of the rules and
apply it to the string. Each of the rules has the form <!-- MATH
$A\rightarrow
\alpha$
-->
A , where A is an uppercase letter and is a string
of lowercase and/or uppercase letters. Applying such a rule to a
string is to replace an occurrence of the letter A in the string to
the string . That is, when the string has the form ``<!-- MATH
$\beta
A\gamma$
-->

A'', where and are arbitrary (possibly empty)
strings of letters, applying the rule rewrites it into the string
``<!-- MATH
$\beta\alpha\gamma$
-->
''. If there are two or more occurrences of A
in the original string, an arbitrary one of them can be chosen for the
replacement.

Below is an example set of rules.

S	<!-- MATH $\rightarrow$ -->	aAB		(1)
A	<!-- MATH $\rightarrow$ -->			(2)
A	<!-- MATH $\rightarrow$ -->	Aa		(3)
B	<!-- MATH $\rightarrow$ -->	AbbA		(4)

Applying the rule (1) to ``S'', ``aAB'' is obtained. Applying (2) to it results in ``aB'', as A is replaced by an empty string. Then, the rule (4) can be used to make it ``aAbbA''. Applying (3) to the first occurrence of A makes it ``aAabbA''. Applying the rule (2) to the A at the end results in ``aAabb''. Finally, applying the rule (2) again to the remaining A results in ``aabb''. As no uppercase letter remains in this string, ``aabb'' is a legitimate name.

We denote such a rewriting process as follows.

S    aAB    aB    aAbbA    aAabbA    aAabb    aabb

Linguists of the country may sometimes define a ridiculous rule set such as follows.

S		sA		(1)
A		aS		(2)
B		b		(3)

The only possible rewriting sequence with this rule set is:

S    sA    saS    sasA     ^...

which will never terminate. No legitimate names exist in this case. Also, the rule (3) can never be used, as its left hand side, B, does not appear anywhere else.

It may happen that no rules are supplied for some uppercase letters appearing in the rewriting steps. In its extreme case, even S might have no rules for it in the set, in which case there are no legitimate names, of course. Poor nameless babies, sigh!

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