You are given a grid with n \times m cells. Two grid cells are neighbors if they share a border.

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.