고대 석판 | cho.sh

문제

수십 년 전, 고고학자들은 어느 고대 신전에서 문자로 뒤덮인 석판을 발견했다. 사용된 기호 자체는 이미 알려져 있었지만, 글 전체가 어떻게 암호화되었는지는 오랫동안 수수께끼로 남아 있었다. 그런데 작년, 첫 번째 신전과 같은 지역에서 또 다른 신전이 발견되었다. 내부 구조가 첫 번째와 매우 비슷해 같은 시기에 지어진 것으로 여겨진다. 두 번째 신전에도 석판이 있었으나 그 내용은 사뭇 달랐다. 1년간의 연구 끝에, 고고학자들은 이 두 번째 석판들이 첫 번째 신전의 글을 해독하는 데 필요한 규칙(코드)을 담고 있다는 가설을 세웠다.

여러분의 임무는 고고학자들이 제안한 규칙을 적용해 석판에 적힌 글을 해독하는 과정을 자동화하는 프로그램을 작성하는 것이다.

규칙에는 두 종류가 있다: PERM과 SHIFT. 두 규칙 모두 다음 세 가지 대상 중 하나에 적용된다: 글의 줄(L), 단어(W), 문자(C).

PERM 규칙은 문자열 PERM, 공백 한 칸, 대상을 나타내는 문자, 그리고 공백으로 구분된 하나 이상의 인덱스 쌍으로 이루어진다. 각 인덱스 쌍 i,j는 두 양의 정수 $i$ 와 $j$ 를 쉼표 하나로 이어 붙인 것이다.

대상에 따라, PERM 규칙은 각 인덱스 쌍 $i, j$ 에 대해 왼쪽에서 오른쪽 순서로 다음을 수행한다:

L: $i$ 번째 줄과 $j$ 번째 줄을 서로 바꾼다.
W: 모든 줄에서 $i$ 번째 단어와 $j$ 번째 단어를 서로 바꾼다.
C: 모든 줄의 모든 단어에서 $i$ 번째 문자와 $j$ 번째 문자를 서로 바꾼다.

교환할 대상 중 하나라도 존재하지 않으면 그 교환은 건너뛴다. 예를 들어 PERM W 2,7은 모든 줄에서 2번째와 7번째 단어를 바꾸라는 뜻이지만, 어떤 줄에는 단어가 다섯 개뿐일 수 있다. 그런 줄에서는 아무것도 하지 않고, 단어가 일곱 개 이상인 다른 모든 줄에서만 교환을 수행한다.

SHIFT 규칙은 문자열 SHIFT, 공백 한 칸, 대상 문자, 공백 한 칸, 그리고 정수 $k$ 로 이루어진다. 이 규칙은 대상을 $|k|$ 번 이동시키며, $k > 0$ 이면 왼쪽(줄의 경우 위쪽) 방향, $k < 0$ 이면 오른쪽(줄의 경우 아래쪽) 방향으로 이동한다. 한 번의 이동은 다음과 같다:

L: 왼쪽(위) 이동이면 모든 줄이 한 줄씩 위로 올라가고 첫 줄이 마지막 줄이 된다. 오른쪽(아래) 이동이면 모든 줄이 한 줄씩 내려가고 마지막 줄이 첫 줄이 된다.
W: 왼쪽 이동이면 각 줄의 단어가 한 칸씩 왼쪽으로 가고 첫 단어가 마지막 단어가 된다. 오른쪽 이동이면 그 반대이다.
C: 왼쪽 이동이면 각 단어의 문자가 한 칸씩 왼쪽으로 가고 첫 문자가 마지막 문자가 된다. 오른쪽 이동이면 그 반대이다.

$k = 0$ 이면 아무 이동도 하지 않는다.

입력

첫째 줄에는 시나리오의 수, 즉 해독해야 할 석판의 개수가 주어진다.

각 석판마다, 먼저 해독할 글의 줄 수 $l$ $(0 \le l \le 1000)$ 이 한 줄에 주어진다. 이어지는 $l$ 개의 줄에 그 글이 주어지며, 각 줄의 길이는 1000자를 넘지 않는다. 그다음 줄에는 적용할 규칙의 수 $r$ $(0 \le r \le 1000)$ 이 주어지고, 이어지는 $r$ 개의 줄에 위에서 설명한 형식의 규칙들이 주어진다.

글의 단어는 (알파벳뿐 아니라) 임의의 문자들이 공백 하나로 구분된 수열로 간주한다. 주어지는 글의 어떤 줄도 공백으로 시작하거나 끝나지 않지만, 줄 전체가 비어 있을 수는 있다.

출력

각 시나리오의 출력은 Scenario #i: 형태의 줄로 시작한다. 여기서 $i$ 는 1부터 시작하는 시나리오 번호이다. 그다음 모든 규칙을 적용한 뒤의 글 $l$ 개의 줄을 출력한다. 연속한 두 시나리오 사이는 빈 줄 하나로 구분한다.