24415번 - 편지

현수는 요즘 "Bell" 이라는 게임을 즐겨 하고 있다. "Bell" 게임에서는 상대방에게 영문 대문자로 이루어진 편지를 보낼 수 있는데, 편지의 내용을 입력하면 특이하게도 편지 자체가 조종할 수 있는 캐릭터가 된다. 캐릭터가 이동하는 도중에는 장애물이 등장하는데, 장애물과 부딪힐 경우 편지는 데미지를 입으며 아래 둘 중 하나의 규칙에 의해서 내용이 바뀌어버린다.

• 편지의 서로 다른 위치의 문자 2개를 교환한다.
• 편지의 특정 위치의 문자를, 해당 문자로부터 알파벳 순서에 의하여 $x$ 번째 뒤에 오는 문자로 변경한다. Z 뒤에는 다시 A 가 오는 것으로 한다.

게임이 시작될 때마다, 편지를 변경하는 규칙들의 목록이 랜덤하게 생성된다. 이 규칙은 캐릭터가 데미지를 입을 때마다 목록 순서대로 적용되며, 목록의 끝에 도달했을 경우 다시 처음으로 돌아간다. 수식으로 표현하면, 규칙 목록의 길이가 $C$, 현재 입은 데미지가 $i$ 번째 데미지일 경우, 편지에는 $((i - 1)\bmod C) + 1$ 번째 규칙이 적용된다.

현수의 원래 편지 내용, 규칙의 목록과 편지가 데미지를 입은 횟수가 주어질 때, 모든 데미지를 입은 후의 편지의 내용이 무엇인지 구하는 프로그램을 작성해 보자.

첫번째 줄에는 공백을 사이에 두고 현수가 작성한 편지의 길이 $N$, 규칙 목록의 길이 $C$, 데미지를 입은 횟수 $K$ 가 정수로 주어진다. $(1 \le N \le 100, 1 \le C \le 10^5, 1 \le K \le 10^{12})$

두번째 줄에는 현수가 작성한 편지가 길이 $N$ 의 문자열로 주어진다.

세번째 줄부터 $C$ 개의 줄에 걸쳐 규칙 목록이 주어진다. 규칙은 다음 둘 중 하나의 형태이며, index 는 0부터 시작한다.

• S i j : 편지의 $i$ 번째 index 와 $j$ 번째 index 의 문자를 교환한다. $(0 \le i, j \lt N, i \ne j)$
• A i x : 편지의 $i$ 번째 index 의 문자를 해당 문자의 $x$ 번째 뒤에 오는 문자로 변경한다. $(0 \le i \lt N, 1 \le x \le 25)$

$K$ 번 데미지를 입은 후의 편지의 내용을 출력한다.