단어

Wright 박사의 수업에서 변형된 L-시스템을 공부하고 있다. 필요한 내용은 다음과 같다.

두 글자 알파벳 ${a, b}$ 위에서 길이가 $n$인 단어를 생각한다. 이 단어는 순환(cyclic) 단어로, $n$가지 순환 이동(cyclic shift) 형태 중 어느 것으로도 쓸 수 있으며, 첫 글자와 마지막 글자는 서로 이웃으로 취급한다.

재작성 규칙은 위치 $i$의 글자를 위치 $i-2$, $i$, $i+1$의 글자에 따라 바꾼다(인덱스는 순환으로 계산한다). 한 단계에서 단어의 모든 글자를 동시에 재작성한다.

시작 단어와 재작성 규칙의 집합이 주어질 때, $s$번 재작성한 뒤 단어가 어떤 모습인지 구하여라.

입력은 여러 개의 블록으로 이루어지며, 각 블록은 하나의 시스템을 설명한다.

• 첫째 줄에는 단어의 길이를 나타내는 정수 $n$이 주어진다 ($2 < n < 16$).
• 둘째 줄에는 시작 단어가 주어지며, 소문자 a와 b로만 이루어져 있다.
• 그다음 여덟 줄에는 각각 네 글자 $c_1 c_2 c_3 c_4$가 주어지며, 하나의 재작성 규칙을 나타낸다. 위치 $i-2$의 글자가 $c_1$, 위치 $i$의 글자가 $c_2$, 위치 $i+1$의 글자가 $c_3$이면, 재작성 후 위치 $i$의 글자는 $c_4$가 된다. 여덟 개의 규칙은 올바르고 완전하다($c_1 c_2 c_3$의 모든 조합을 빠짐없이 덮는다).
• 블록의 마지막 줄에는 정수 $s$가 주어진다 ($0 \le s \le 2000000000$).

입력의 끝까지 모든 블록을 처리한다.

각 블록마다 한 줄에 $s$번 재작성한 뒤의 단어를 출력한다. 단어는 순환 단어이므로 $n$가지 이동 형태로 쓸 수 있는데, a < b라고 할 때 그중 사전순으로 가장 작은 형태를 출력한다.