Wheat Harvest

Interview

Time limit1sMemory limit128 MB

Summary

Find each connected block of 1s, order blocks by area, and label every cell with its block's rank.

Level: Medium4 of 10
Topics: Graph, DFS, Sorting
Solved: No attempts yet

Problem

Zoran lives on a farm and owns the biggest combine harvester in the village. The crop buyout went badly this year, but Zoran still sowed wheat in several places. Harvest time has arrived and he does not feel much like working.

Even so, he harvests one wheat field each day. The field he harvests that day is the smallest one by area among the fields still standing.

Zoran's land is an $R \times S$ grid of squares. For every square it is known whether Zoran sowed wheat there. Two squares are adjacent if they share a side.

A wheat field is a maximal set of sown squares connected through adjacency. The left table in the picture below contains four fields. The right table gives each field the number of the day on which Zoran harvests it.

Write a program that determines, for every sown square, the day on which Zoran harvests it.

Input

The first line contains natural numbers $R$ and $S$ , the size of Zoran's land ( $1 \le R, S \le 50$ ).

Each of the next $R$ lines contains $S$ characters, either '0' or '1'. A '0' is a square without wheat, and a '1' is a square with wheat.

The number of wheat fields is less than 10, and no two wheat fields have the same area.

Output

Print $R$ lines of $S$ characters each. A square without wheat gets '0', and every other square gets the ordinal number of the day on which that square is harvested.

Examples6

Example 1

Input

Expected output

Example 2

Input

Expected output

Example 3
Input
```
1 1
1
```
Expected output
```
1
```
Example 4
Input
```
1 8
10110111
```
Expected output
```
10220333
```
Example 5
Input
```
4 1
1
0
1
1
```
Expected output
```
1
0
2
2
```
Example 6
Input
```
2 3
100
011
```
Expected output
```
100
022
```