아기에게 가장 좋은 이름

29XX년, 지구 어딘가에 있는 한 작은 나라의 정부는 문화적 고유성을 지키기 위해, 사람들의 이름(first name)을 그들 문화의 전통적인 이름으로만 제한하는 법을 도입했다. 이 나라의 언어학자들은 매년 한 번 규칙의 집합을 정하며, 그해에는 그 규칙에 맞는 이름만 허용된다. 또한 이 법은 각 사람이 자신의 생년월일로부터 계산된 특정 길이의 이름을 쓰도록 요구하는데, 그렇지 않으면 너무 많은 사람이 똑같이 인기 있는 이름을 쓰게 되기 때문이다. 이 법이 제정된 이래, 새로 태어난 아기의 부모가 흔히 하는 일은 주어진 길이의 적법한 이름들 가운데 알파벳 순서로 가장 앞서는 이름을 찾는 것이다. 그들의 문화에서는 알파벳 순서가 앞선 이름이 여러 이점을 주기 때문이다.

적법한 이름이란, 대문자 S 하나로 이루어진 초기 문자열 "S"에 규칙 집합을 반복해서 적용하여 얻을 수 있는, 소문자로만 이루어진 문자열을 말한다.

문자열에 규칙 집합을 적용한다는 것은 규칙 중 하나를 골라 그 문자열에 적용하는 것이다. 각 규칙은 $A \to \alpha$ 꼴이며, 여기서 $A$는 대문자이고 $\alpha$는 소문자와/또는 대문자로 이루어진 문자열이다. 이러한 규칙을 문자열에 적용한다는 것은 문자열 안의 문자 $A$ 하나를 문자열 $\alpha$로 바꾸는 것이다. 즉, 문자열이 $\beta A \gamma$ 꼴일 때(여기서 $\beta$와 $\gamma$는 임의의, 비어 있을 수도 있는 문자열이다), 규칙을 적용하면 $\beta \alpha \gamma$로 바뀐다. $A$가 두 번 이상 나타나면 그중 아무거나 하나를 골라 바꿀 수 있다.

다음은 규칙 집합의 예이다.

1. $S \to aAB$
2. $A \to$ (빈 문자열)
3. $A \to Aa$
4. $B \to AbbA$

"S"에 규칙 (1)을 적용하면 "aAB"가 된다. 여기에 (2)를 적용하면 $A$가 빈 문자열로 바뀌어 "aB"가 된다. 그다음 규칙 (4)를 쓰면 "aAbbA"가 된다. 첫 번째 $A$에 (3)을 적용하면 "aAabbA"가 된다. 끝에 있는 $A$에 (2)를 적용하면 "aAabb"가 된다. 마지막으로 남은 $A$에 (2)를 다시 적용하면 "aabb"가 된다. 대문자가 하나도 남지 않았으므로 "aabb"는 적법한 이름이다. 이러한 재작성 과정을 다음과 같이 나타낸다.

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

언어학자들은 때때로 다음과 같은 터무니없는 규칙 집합을 정하기도 한다.

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

이 규칙 집합으로 가능한 유일한 재작성 순서는

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

이며, 이는 결코 끝나지 않는다. 따라서 이 경우에는 적법한 이름이 존재하지 않는다. 또한 규칙 (3)은 그 좌변인 $B$가 다른 어디에도 나타나지 않으므로 결코 쓰일 수 없다.

재작성 과정에 나타나는 어떤 대문자에 대해 규칙이 하나도 주어지지 않는 경우도 있다. 극단적으로는 $S$조차 규칙이 없을 수 있으며, 그런 경우에는 당연히 적법한 이름이 존재하지 않는다.

이제 여러분의 과제는, 주어진 규칙 집합에 맞고 주어진 길이를 가지는 적법한 이름들 가운데 알파벳 순서로 가장 앞서는 이름을 찾는 프로그램을 작성하는 것이다.

입력은 여러 개의 데이터셋이 이어지고, 마지막에 공백으로 구분된 두 개의 0이 있는 줄이 와서 입력의 끝을 나타낸다. 각 데이터셋은 공백으로 구분된 두 정수 $n$과 $l$이 있는 줄로 시작한다. 여기서 $n$($1 \le n \le 50$)은 규칙의 개수이고, $l$($0 \le l \le 20$)은 요구되는 이름의 길이이다. 그 줄 다음에는 각각 하나의 규칙을 나타내는 $n$개의 줄이 온다. 이 줄들은 각각 대문자 A부터 Z 중 하나로 시작하고, 이어서 문자 "="("$\to$" 대신)가 오며, 그 뒤에 규칙의 우변인 AZ와 az 문자로 이루어진 문자열이 온다. 이 문자열의 길이는 10을 넘지 않으며 0일 수도 있다. 규칙을 나타내는 줄에는 공백이 나타나지 않는다.

출력은 입력과 같은 순서로 각 데이터셋에 대한 답을 보여 주는 줄들로 이루어진다. 각 줄은 소문자 a~z로 이루어진 문자열로, 해당 입력 데이터셋에 주어진 규칙과 길이에 맞는, 알파벳 순서로 첫 번째인 적법한 이름이다. 주어진 규칙 집합에 그 길이에 맞는 문자열이 없으면, 그에 해당하는 출력 줄에는 하이픈 하나 "-"를 출력한다. 출력에는 다른 어떤 문자도 포함되지 않는다.