Breaking a Wall and Moving 4

Interview

Time limit2sMemory limit512 MB

Summary

For each wall cell in an N by M binary grid, break it and print the size of the reachable open region modulo 10, leaving empty cells as 0.

Level: Medium6 of 10
Topics: Graph, BFS, Union-find, Matrix
Solved: No attempts yet

Problem

There is a map represented by an N×M matrix. In the map, 0 marks a cell you can move through, and 1 marks a wall you cannot move through. To move from one cell to another, the two cells must be adjacent. Two cells are adjacent when they share an edge.

For each wall, do the following.

Break the wall and turn it into a cell you can move through.
Count the number of cells reachable from that position.

The cells reachable from a cell are the cells adjacent to it up, down, left, and right.

Input

The first line gives N (1 ≤ N ≤ 1,000) and M (1 ≤ M ≤ 1,000). The next N lines give the map as M digits each.

Output

Print the answer in the form of a map. For a cell that was originally empty, print 0. For a cell that was a wall, print the number of reachable cells modulo 10.

Examples2

Example 1
Input
```
3 3
101
010
101
```
Expected output
```
303
050
303
```

Example 2

Input

Expected output