Linden 시장 시스템

면접 대비

시간 제한2초메모리 제한1024 MB

요약

주어진 치환 규칙을 시작 문자열의 모든 글자에 m번 적용한 뒤의 문자열을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 문자열, 시뮬레이션, 해시맵
정답자: 아직 제출이 없습니다

문제

Aristid는 Linden이라는 마을의 시장이다. 그와 마을 사람들은 프랙탈을 좋아한다. 어느 날 Aristid는 나무를 유전적으로 바꿔 수학적으로 보기 좋은 구조를 갖게 하기로 한다. 린덴 사람들은 나무가 충분히 "나무답게" 보여야만 이 아이디어를 지지하겠다고 한다. 그래서 Aristid는 현실적인 나무 모양을 만드는 다음 시스템을 고안했다. 조금 허영심이 있는 그는 이 시스템을 Linden Mayor System이라고 이름 붙였다.

문자열 $S_0$ 로 시작한다. 이것이 나무 전체를 만드는 씨앗이다. 다음으로 나무의 가지가 뻗는 방식을 규칙으로 정한다. 규칙 $x \rightarrow y$ 는 문자 $x$ 를 문자열 $y$ 로 바꾼다는 뜻이다. 이 규칙을 $S_0$ 에 적용하면 새 문자열 $S_1$ 이 만들어진다. 규칙은 몇 번이고 반복해서 적용할 수 있다. 일반적으로 $S_n$ 에서 $S_{n+1}$ 을 만들 때는 $S_n$ 의 모든 문자를 규칙에 따라 바꾼다. 규칙이 없는 문자는 종결 문자이며, 바뀌지 않는다.

예를 들어 시작 문자열 A와 규칙 A $\rightarrow$ AB, B $\rightarrow$ A를 보자. 처음 네 번의 반복은 다음과 같다.


$S_0$ :	A	시작 문자열이다.
$S_1$ :	AB	규칙 A $\rightarrow$ AB에 의해 A가 AB로 바뀐다. 규칙 B $\rightarrow$ A는 적용되지 않는다.
$S_2$ :	ABA	다시 A는 AB로 바뀌고, B는 규칙 B $\rightarrow$ A에 의해 A로 바뀐다.
$S_3$ :	ABAAB	모든 A에는 규칙 A $\rightarrow$ AB를, 모든 B에는 규칙 B $\rightarrow$ A를 계속 적용한다.
$S_4$ :	ABAABABA	네 번 반복한 후의 문자열이다.

입력

첫 줄에 두 정수 $n$ 과 $m$ 이 주어진다. $0 \leq n \leq 26$ , $0 \leq m \leq 5$ 이다.

이어서 $n$ 개의 줄에 규칙이 주어진다. 각 줄은 $x$ -> $y$ 형태이며, $x$ 가 $y$ 로 바뀐다는 뜻이다. $x$ 와 $y$ 는 A부터 Z까지의 대문자만 포함한다. $y$ 의 길이는 최대 5이다.

마지막 줄에는 시작 문자열 $S_0$ 가 주어진다. 길이는 최대 30이며, A부터 Z까지의 대문자만 포함한다.

출력

$m$ 번 반복한 후의 문자열 $S_m$ 을 출력한다.

예제1

예제 1
입력
```
2 4
A -> AB
B -> A
A
```
예상 출력
```
ABAABABA
```