Problem Description

Xiao Lan has recently become addicted to a game called "Pixel Placement". The game is played on an $n \times m$ grid board. The board has $n$ rows, and each row contains $m$ cells. The player's task is to fill the $n \times m$ cells with pixels, using only two colors: black or white.

Some cells contain an integer digit $x(0 \leq x \leq 9)$. This means that among the $9$ cells consisting of this cell plus the eight adjacent cells in the surrounding directions (up, down, left, right, upper-left, upper-right, lower-left, lower-right), there are exactly $x$ cells that must be filled with black.

The player needs to fill the grid while satisfying all numeric constraints. Please help Xiao Lan complete it. The problem guarantees that a solution exists for all testdata and that the solution is unique.

Input Format

The first line contains two integers $n, m$, separated by a space, representing the board size.

The next $n$ lines each contain $m$ characters, describing the board layout. A character may be a digit $0 \sim 9$, meaning a number on the grid. It may also be an underscore ($\text{ASCII}$ code $95$), meaning a normal cell without a number.

Output Format

Output $n$ lines, each containing $m$ characters, representing the answer. If a cell is filled with white, output the character 0. If a cell is filled with black, output the character 1.

6 8
_1__5_1_
1_4__42_
3__6__5_
___56___
_688___4
_____6__

00011000
00111100
01000010
11111111
01011110
01111110

Hint

Sample Explanation

In the figure above, the left side is the board layout corresponding to the sample input, and the right side is the solution to that game. For example, the cell at row $3$, column $1$ contains the number $3$. Around it, there are exactly $3$ cells filled with black: the cells at row $3$, column $2$, row $4$, column $1$, and row $4$, column $2$.

Constraints

For $50\%$ of the test cases, $1 \leq n, m \leq 5$.

For all test cases, $1 \leq n, m \leq 10$.

Translated by ChatGPT 5