정처 없이 떠돌기

수많은 콘솔 롤플레잉 게임의 마을에는 특별한 역할 없이 정처 없이 돌아다니며 플레이어가 말을 걸어 주기를 기다리는 단역 캐릭터(NPC)가 가득합니다. 여러분은 새 게임에 등장하는 이런 마을 NPC들의 이동 처리를 구현해야 합니다.

각 NPC는 다음과 같은 몇 가지 간단한 명령으로 이루어진 이동 스크립트를 가집니다.

스크립트를 작성하는 사람이 항상 꼼꼼한 것은 아니어서, 스크립트가 NPC에게 벽을 뚫고 지나가거나 지도 밖으로 나가라고 시키는 경우가 있습니다. 이런 일이 생기면, NPC를 유효하지 않은 칸으로 옮기게 될 모든 이동 스텝은 PAUSE로 바뀝니다. 예를 들어 다음과 같은 작은 마을 조각이 있을 때,

...#
.1.#
...#

1로 표시된 NPC의 다음 명령이 EAST 5라면, 이 명령은 즉석에서 EAST 1 다음에 PAUSE 4가 오는 형태로 변환됩니다. 이 변환은 스크립트가 순환형(cyclic)인지 왕복형(reversible)인지 판정하기 전에 먼저 이루어져야 합니다.

스크립트가 끝났을 때 NPC가 처음 위치로 돌아와 있으면 그 스크립트는 순환형이며, 이런 스크립트는 그대로 무한히 반복됩니다. 그렇지 않으면 그 스크립트는 왕복형입니다. 스크립트가 끝났을 때 NPC가 처음 위치로 돌아와 있지 않으면, NPC는 (이미 변환된) 스크립트를 뒤집은 복사본을 실행합니다. 이때 방향은 서로 바뀌고(WEST↔EAST, NORTH↔SOUTH) PAUSE는 그대로 유지됩니다. 그 결과 캐릭터는 처음 위치로 되돌아옵니다.

이 문제에서는 어떤 두 NPC도 같은 시각에 같은 칸을 차지하려 하지 않는다고 가정해도 됩니다. 다만 한 NPC가 어떤 칸을 떠나는 바로 그 턴에 다른 NPC가 그 칸으로 들어오는 것은 유효한 동작입니다.

시뮬레이션은 턴 0에서 시작합니다. 지도와 스크립트를 가진 NPC들이 주어질 때, 주어진 수만큼의 턴이 지난 뒤 마을의 모습이 어떻게 되는지 출력하세요.

입력의 첫 줄에는 데이터 집합의 개수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어집니다. 각 데이터 집합은 다음으로 구성됩니다.

• 이 마을의 NPC 수를 나타내는 정수 C (1 ≤ C ≤ 35)가 적힌 한 줄.
• 마을의 높이와 너비를 나타내는 두 정수 H와 W (1 ≤ H, W ≤ 40)가 적힌 한 줄.
• 마을을 나타내는 H개의 줄. 각 줄은 W개의 문자로 이루어지며 다음 의미를 가집니다.
  • # 는 벽이나 지나갈 수 없는 장애물을 나타냅니다.
  • . 는 빈 칸을 나타냅니다.
  • 숫자나 대문자는 NPC의 시작 칸을 나타냅니다. 1 은 첫 번째 NPC, 2 는 두 번째 NPC이며, 9까지 이어진 뒤 A 는 열 번째, B 는 열한 번째 NPC를 나타내고, 이런 식으로 계속됩니다. NPC의 시작 위치 아래 칸은 빈 칸으로 취급합니다.
• NPC 스크립트를 설명하는 C개의 블록. 각 블록은 다음과 같습니다.
  • 한 문자와 정수 L (1 < L < 20)이 공백으로 구분되어 적힌 한 줄. 여기서 문자는 어떤 NPC의 지도상 기호이고, L은 그 NPC 스크립트의 길이입니다.
  • 그 NPC의 스크립트를 위 형식으로 나타낸 L개의 줄. 인자 값은 40을 넘지 않습니다.
• 시뮬레이션할 턴 수를 나타내는 정수 T (1 ≤ T ≤ 1000000)가 적힌 한 줄.

각 데이터 집합마다 먼저 DATA SET #k 라는 제목을 출력합니다. 여기서 k는 첫 번째 데이터 집합이면 1, 두 번째면 2와 같이 매겨집니다. 그다음 H개의 줄에 마을 지도를 출력하되, 입력과 같은 기호를 사용하고 각 NPC는 주어진 턴 수가 지난 뒤 자신이 있는 칸에 그립니다.