NAFTA

The cross section of an oil field is a rectangle divided into $R$ rows and $S$ columns of cells. A cell that holds oil is marked with a digit from 0 to 9, and that digit is the amount of oil in the cell. Every other cell is marked with the character ..

A drill is made by choosing a column, raising a tower above ground in that column, and drilling straight down through the whole column, possibly passing through one or more layers of oil.

Once every hole is drilled, pumping starts. All the oil leaves each pool that a drill passes through, where a pool is a set of oil cells connected up, down, left or right. In other words, the oil leaves every cell that is reachable from a cell the drill passes through by moving up, down, left or right over cells marked with digits.

In the third example two drill holes empty the whole field.

Write a program that, for the given oil field and for each integer $K$ with $1 \le K \le S$, determines the largest total amount of oil that can be pumped out with at most $K$ drills.

The first line contains the integers $R$ and $S$, the number of rows and the number of columns of the cross section ($1 \le R, S \le 100$).

Each of the next $R$ lines contains $S$ characters describing one row of the cross section. Each character is either . or a digit from 0 to 9.

Print $S$ integers, each on its own line. The $K$-th integer is the largest total amount of oil that can be pumped out with at most $K$ drills.