지뢰 찾기

지뢰 찾기 게임에서는 격자가 주어지고, 일부 칸에는 지뢰가 숨겨져 있습니다. 안전하다고 판단한 칸을 열었을 때, 그 칸에 지뢰가 있었다면 게임에서 지고, 지뢰가 없었다면 대각선을 포함한 최대 8개의 이웃 칸 중 몇 개에 지뢰가 있는지를 알려 줍니다.

일부만 공개된 지뢰 찾기 격자가 주어질 때, 아직 열지 않은 각 칸에 대해 반드시 지뢰가 있는지, 절대 지뢰가 없는지, 아니면 주어진 정보만으로는 판단할 수 없는지를 결정하세요.

첫 번째 줄에는 격자의 너비 $W$와 높이 $H$가 정수로 주어집니다 ($1 \le W \le 30$, $1 \le H \le 16$).

이어지는 $H$개의 줄은 격자의 각 행을 나타냅니다.

• 숫자 0–8은 지뢰가 없는 공개된 칸이며, 그 숫자는 대각선을 포함한 이웃 칸 중 지뢰가 있는 칸의 개수입니다.
• 마침표 .는 아직 열지 않은 칸입니다.

공개된 칸들과 모순되지 않는 지뢰 배치의 수는 많아야 수만 개이며, 그러한 배치가 적어도 하나는 반드시 존재합니다.

입력과 같은 형태로 격자를 한 줄에 한 행씩 출력하세요. 각 칸은 다음과 같이 표시합니다.

• 공개된 칸은 그 숫자를 그대로 출력합니다.
• 가능한 모든 배치에서 지뢰가 있는 칸은 *로 표시합니다.
• 가능한 모든 배치에서 지뢰가 없는(안전한) 칸은 공백 하나로 표시합니다.
• 그 밖의 칸(지뢰 여부를 확정할 수 없거나, 공개된 칸과 인접하지 않은 칸)은 .로 그대로 둡니다.