403754: GYM101257 F Islands II

The world of Bitland is an N × M grid with K islands numbered from 1 through K. An island is a group of connected cells. Two cells are connected if you can start in one of them and reach the other one by moving only to adjacent cells. Two cells are adjacent if they share a side.

The picture above shows a world with 9 islands, each island is represented by a unique color.

As you can see, in Bitland, islands may contain other islands, and so to avoid ambiguity, Bitland was built in a way that will never allow the following situation:

If you don't see why it's ambiguous, well, we can't tell whether the blue island is contained inside the green one or not.

More formally, for any 2 × 2 sub-grid of Bitland, if the cells on one of the two diagonals belong to the same island, then there's at least one more cell that belongs to the same island in this sub-grid.

Your task this time is to find the number of sub-islands contained in each island in Bitland.

The first line of input contains two space-separated integers, N and M (1 ≤ N, M ≤ 1000), the number of rows and columns of the grid, respectively.

Each of the following N lines contains M integers, each integer is between 1 and K, where K is the number of islands.

It is guaranteed that the input is valid and matches the description of the problem statement.

On a single line, print K integers, the i^th integer represents the number of sub-islands contained in the i^th island.

5 5
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

2 1 0

5 6
1 1 1 1 1 1
1 2 2 4 4 1
1 2 3 3 4 1
1 2 2 4 4 1
1 1 1 1 1 1

3 0 0 0