유역 나누기 (Large)

지질학자는 빗물이 흘러내리는 방향에 따라 땅을 여러 구역으로 나눈다. 이렇게 나눈 구역을 배수 유역이라고 한다.

각 칸의 고도를 담은 2차원 배열, 즉 고도 지도가 주어진다. 같은 배수 유역에 속한 칸이 같은 이름표를 받도록 지도의 모든 칸에 이름표를 붙여야 한다. 규칙은 다음과 같다.

• 한 칸의 물은 인접한 네 칸 중 최대 한 칸으로 흘러내린다.
• 어떤 칸에 인접한 네 칸 가운데 그 칸보다 고도가 낮은 칸이 하나도 없으면 물은 흐르지 않는다. 이런 칸을 싱크라고 한다.
• 그렇지 않으면 물은 인접한 칸 중 고도가 가장 낮은 칸으로 흐른다.
• 고도가 가장 낮은 인접한 칸이 여럿이면 북, 서, 동, 남 순서에서 먼저 오는 방향을 고른다.

직접 또는 다른 칸을 거쳐 같은 싱크로 흘러드는 칸은 모두 같은 배수 유역에 속한다. 유역마다 서로 다른 알파벳 소문자 하나를 이름표로 붙이는데, 지도의 각 행을 위에서 아래로 이어 붙인 문자열이 사전순으로 가장 앞서도록 붙인다. 그래서 가장 북서쪽 칸이 속한 유역의 이름표는 항상 'a'다.

첫째 줄에 지도의 개수 $T$가 주어진다. 이어서 지도 $T$개가 주어진다. 각 지도의 첫째 줄에는 지도의 높이 $H$와 너비 $W$가 칸 수로 주어진다. 다음 $H$개의 줄에는 북쪽 행부터 남쪽 행까지 한 줄에 한 행씩 주어지고, 각 줄에는 서쪽 칸부터 동쪽 칸까지 고도 $W$개가 공백으로 구분되어 주어진다.

• $1 \le T \le 100$
• $1 \le H \le 100$, $1 \le W \le 100$
• 고도는 $0$ 이상 $10000$ 미만의 정수다.
• 한 지도의 배수 유역은 최대 26개다.

지도마다 $H+1$개의 줄을 출력한다. 첫 줄은 다음 형식으로 출력한다.

Case #X:

여기서 $X$는 지도의 번호이고 1부터 시작한다. 이어지는 $H$개의 줄에는 입력에 나온 것과 같은 순서로 각 칸의 유역 이름표를 출력한다. 한 줄 안의 이름표는 공백 하나로 구분한다.

첫 번째 예제의 첫 지도에서는 북동쪽 모서리와 남서쪽 모서리가 싱크다. 대각선에 놓인 칸의 물은 고도가 더 낮은 쪽(6이 아니라 5)으로 흐르므로 남서쪽 싱크로 흘러든다.