30036번 - INK

문제

INK는 하얀 사각형을 조종하여, 다양한 위험 요소를 피해 도착 지점으로 도달하는 플랫포머 퍼즐 게임이다. 플레이어가 조종하는 하얀 사각형은 점프할 때마다 다양한 색의 잉크를 흩뿌린다. 흩뿌려진 잉크는 투명한 장애물에 부딪혀, 투명했던 장애물을 염색시킨다. 그 이후로 플레이어는 염색된 장애물을 볼 수 있게 된다.

스테이지의 레벨은 $N \times N$ 크기의 그리드로 표현할 수 있다. $(y, x)$는 $y$행 $x$열에 위치한 칸을 의미하며, 칸은 항상 빈칸이거나 장애물 중 하나이다. 스테이지의 레벨에서 게임을 시작하면 플레이어는 스테이지에서 커맨드를 입력하여 사각형을 조종할 수 있다. 스테이지에서 플레이어는 커맨드를 총 $K$번 입력한다. 아래는 커맨드에 대한 설명이다.

• 이동 커맨드
  • 대문자 알파벳 $U,ドル $D,ドル $L,ドル $R$로 4가지이고 각각 상, 하, 좌, 우 방향으로 1ドル$칸 이동함을 의미한다.
  • 이동 커맨드에 따라 움직였을 때 사각형이 스테이지 밖으로 벗어나거나 장애물과 겹치는 경우 해당 커맨드는 무시된다.
• 잉크 충전 커맨드
  • 잉크 충전 커맨드는 소문자 알파벳 $j$이다.
  • 잉크 충전 커맨드를 입력받으면 사각형이 가지고 있는 잉크의 양이 1ドル$ 증가한다.
  • 게임 시작 시 사각형이 가지고 있는 잉크의 양은 0ドル$이다.
• 점프 커맨드
  • 점프 커맨드는 대문자 알파벳 $J$이다.
  • 점프 커맨드를 입력받으면 사각형이 제자리에서 점프하면서 잉크가 흩뿌려지며, 이때 잉크의 양은 사각형이 가지고 있는 잉크의 양과 같다.
    • 잉크의 색상이 $c_i$이고 잉크의 양이 $m_i$인 잉크가 $(y_i, x_i)$ 지점에서 흩뿌려졌을 때 $|y_i-a|+|x_i-b| \le m_i$를 만족하는 $(a, b)$ 칸이 장애물 칸이라면 $c_i$로 칠해진다.
    • 만약 장애물 칸이 다른 색상으로 이미 칠해져 있다면, 나중에 닿은 잉크의 색상으로 덮어씌워 칠해진다.
  • 점프한 직후 사각형이 가지고 있는 잉크의 양은 0ドル$이 된다.

잉크의 색상은 점프 커맨드 입력 횟수와 잉크 문자열에 의해 결정된다.

• 잉크 문자열
  • 잉크 문자열은 알파벳 대문자로 이루어진 길이가 $I$인 문자열이다.
  • $t \times I + d$번째 점프할 때의 잉크의 색상은 잉크 문자열의 $d$번째 문자가 된다. $(t$는 음이 아닌 정수$;$ 1ドル \le d \le I)$
    • 예를 들어 1ドル$번째 점프는 1ドル$번째 문자, 2ドル$번째 점프는 2ドル$번째 문자, $I$번째 점프는 $I$번째 문자, $I + 1$번째 점프는 1ドル$번째 문자, $I + 2$번째 점프는 2ドル$번째 문자가 된다.

잉크 문자열, 초기 스테이지의 레벨 모습, 플레이어가 입력한 커맨드를 입력받아 커맨드를 모두 실행한 후의 스테이지 모습을 출력하는 프로그램을 작성해 보자.

입력

첫 번째 줄에 정수 $I,ドル $N,ドル $K$가 공백으로 구분되어 주어진다. $(1 \le I, N, K \le 100)$

두 번째 줄에는 잉크 문자열이 주어진다.

세 번째 줄부터 $N$개의 줄에 걸쳐 $N \times N$ 크기의 스테이지가 주어진다. 사각형은 @, 빈칸은 . , 장애물은 #으로 주어진다. 사각형은 항상 1ドル$개만 주어진다.

마지막 줄에는 $K$개의 커맨드가 공백 없이 주어진다.

출력

$N$개의 줄에 걸쳐 $N \times N$ 크기의 최종 스테이지 모습을 출력한다.

사각형은 @로, 빈칸은 . , 염색되지 않은 장애물은 #로, 염색된 장애물은 염색된 잉크의 색상 알파벳 대문자로 출력한다.

제한

힌트