**Time limit:**1.00 s**Memory limit:**512 MB

The grid cells have to be labeled with numbers 1, 2, 3 and 4. There is only one rule: neighbors must have different labels. So you cannot have e.g. a cell with label 1 if there is another cell with label 1 above it, below it, or on its left or right side.

In the input, some of the grid cells are already labeled. All labeled cells already follow the rule that neighbors have different labels.

However, some input cells may be

*empty*. The empty cells form a connected region in the following sense: you can pick any two empty cells $x$ and $y$, and you can walk from $x$ to $y$ so that you step from one empty cell to a neighboring empty cell.

Now your task is to find a way to label

*all*cells with labels 1, 2, 3, and 4 so that as many cells as possible can keep their original labels.

**Input**

The first input line contains two positive integers $n$ and $m$.

Then there are $n$ lines, each of which contains $m$ characters. Each character denotes the input label of one cell: either it is 0 (empty), or one of the values 1, 2, 3, and 4 to indicate a cell that is already labeled.

**Output**

Print the final grid where every cell is labeled. You can print any valid solution.

**Constraints**

- $1 \le n \cdot m \le 10^5$

**Example 1**

Input:

`3 4`

1234

2000

1234

Output:

`1234`

2342

1234

Explanation: All 9 non-empty cells were able to keep their original labels.

**Example 2**

Input:

`3 3`

123

401

132

Output:

`123`

414

132

Explanation: There is no way to label the grid so that 8 cells have their original labels, but there is a way to label the grid so that 7 cells have their original labels.