누리카베

누리카베 퍼즐을 푸는 프로그램을 작성하자.

누리카베는 직사각형 격자 위에서 진행된다. 각 칸은 비어 있거나(. 로 표시) 한 자리 숫자가 적혀 있다. 퍼즐을 풀려면 모든 칸을 흰색(땅) 또는 검은색(바다) 중 하나로 칠해야 하며, 아래 조건을 모두 만족해야 한다. 여기서 섬이란 상하좌우로 이어진 흰색 칸들의 극대 연결 영역을 말한다.

1. 모든 검은색 칸은 하나로 연결되어 있어야 한다.
2. 숫자가 적힌 칸은 반드시 어떤 섬에 속해야 한다.
3. 각 섬에 포함된 흰색 칸의 개수는 그 섬에 들어 있는 숫자와 같아야 한다.
4. 모든 섬에는 숫자가 적힌 칸이 정확히 하나 있어야 한다.
5. 서로 다른 두 섬은 인접(연결)해서는 안 된다.
6. $2 \times 2$ 크기의 검은색 칸 덩어리는 존재할 수 없다.

칸의 인접은 상하좌우로만 판단하며, 대각선은 인접으로 보지 않는다. 입력으로는 항상 정답이 유일한 경우만 주어진다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 퍼즐의 크기 $n$과 $m$이 공백으로 구분되어 주어진다. ($3 \le n, m \le 9$)

이어지는 $n$개의 줄에는 퍼즐의 초기 상태가 주어진다. 각 줄은 $m$개의 문자로 이루어지며, 빈 칸은 .으로, 숫자 칸은 그 칸에 적힌 숫자로 표시된다. 숫자는 항상 한 자리이다.

입력의 마지막 줄에는 0이 두 개 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다 퍼즐을 푼 결과를 출력한다. 검은색 칸은 #으로 표시하고, 흰색 칸은 원래 문자(. 또는 숫자)를 그대로 출력한다. 서로 다른 퍼즐의 출력 사이에는 빈 줄을 하나씩 넣는다.