A-maze-ing Lakes

Interview

Time limit10sMemory limit1024 MB

Summary

Given a binary grid, count the 4-connected components of water tiles and report each component's size in sorted order.

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

Problem

An environmental agency surveys lakes in various places. The survey estimates the size and distribution of lakes by location, and it is the first stage of a larger program. At this stage, the agency estimates from aerial photographs. Because many lakes must be examined, the agency uses a computer program for the task. Specifically, the program receives a two-color image like the one below.

The task is to count the lakes (shown in blue in the image) and find the surface area of each one. The image is a 2D array of tiles, and each tile is either ground or water. Each tile covers one square meter. Given one water tile, its lake contains every water tile reachable from it by moving up, down, left, or right through water tiles only. Diagonal moves are not allowed. You may assume that the tiles on the image border are always ground.

Input

The first line contains two integers N and M, separated by a single space (1 $\le N \le 10^3$ , 1 $\le M \le 10^3$ ). These define an N by M 2D array of tiles. The next N lines each contain a string of exactly M characters. A 0 marks a ground tile, and a 1 marks a water tile.

Output

The first line prints K, the number of distinct lakes. The second line prints K space-separated integers, the sizes of the lakes in square meters, sorted from smallest to largest.

Examples2

Example 1

Input

6 13
0000000000000
0111101111110
0001101000100
0001101000110
0011000011110
0000000000000

Expected output

2
10 15

Example 2

Input

Expected output

1
20