최악의 시나리오

전염병이 빠르게 퍼지고 있어 정부가 감염 지역 지도를 요청했다. 일련의 사건이 일어난 뒤 특정 지역이 최악의 경우 어떤 모습이 되는지 알고 싶어 한다. 정부가 관심을 두는 감염 단계는 네 가지다.

• A 단계: 감염이 아직 이 구역에 닿지 않았다. 감염 사건이 일어나면 이런 구역도 단계가 올라갈 수 있다.
• B 단계: 감염 초기다. 시민 개개인의 이상 행동이 보고되고, 격리가 시작되었으며, 지방 당국이 아직 상황을 통제하고 있다.
• C 단계: 몇몇 곳에서 좀비 무리를 상대하고 있다. 격리는 읍이나 소도시 규모로 이루어진다. 감염은 구역 안에 머물러 있지만 통제를 벗어나며 커지고 있다.
• D 단계: 구역이 경계 통제력을 잃었다. 인접 구역으로 감염이 번지는 것은 시간문제다.

감염 사건은 구역을 더 높은 감염 단계로 밀어 올리는 모든 일을 말한다. 보통 격리 실패, 바이러스 변이, 생물 테러가 원인이다. 어떤 구역에 감염 사건이 일어나면 최악의 경우 그 구역의 단계가 하나 올라간다. D 단계 구역은 단계가 더 올라갈 수 없으므로, 최악의 경우 추가로 겪는 감염 사건마다 창궐이 일어난다. 창궐이 일어나면 인접한 모든 구역이 감염 사건을 한 번씩 더 겪는다. 창궐은 연쇄로 이어지지만, 감염 사건 하나를 처리하는 동안 한 구역에서 창궐은 최대 한 번만 일어난다.

X로 표시된 구역은 통행할 수 없고 사람도 살지 않는 곳이라 감염되지 않으며 단계가 바뀌지 않는다. 두 구역은 격자에서 위, 아래, 왼쪽, 오른쪽으로 바로 맞닿아 있을 때 인접하다. 창궐이 일어나도 감염은 대각선으로 번지지 않는다.

시작 단계가 표시된 구역 격자와 감염 사건이 일어나는 구역 좌표의 목록이 주어진다. 각 감염 사건은 다음 사건을 계산하기 전에 끝까지 처리한다.

첫 줄에 테스트 케이스의 수 $N$ ($1 \le N \le 50$)이 주어진다. 각 테스트 케이스의 첫 줄에는 격자의 너비 $W$ ($1 \le W \le 100$)와 높이 $H$ ($1 \le H \le 100$)가 주어지고, 이어서 격자가 $H$개의 줄에 걸쳐 한 줄마다 $W$개의 문자로 주어진다. 각 구역은 현재 단계를 나타내는 문자로 표시되며, 통행할 수 없는 구역은 X로 표시된다.

격자 다음 줄에는 감염 사건의 수 $I$ ($0 \le I \le 1000$)가 주어진다. 이어지는 $I$개의 줄에는 각각 두 정수 $x$와 $y$가 주어진다. 이 줄은 $x$번째 열(가장 왼쪽 열이 $x = 0$)과 $y$번째 행(가장 위쪽 행이 $y = 0$)에 있는 구역에서 감염 사건이 일어남을 뜻한다.

각 테스트 케이스마다 최악의 경우의 최종 격자를 출력한다. $W$개의 문자로 이루어진 줄을 $H$개 출력하며, 테스트 케이스 사이에는 아무것도 출력하지 않는다.