Oil Field Extraction

You are given an n × m matrix, which represents a cross‐section of an oil field. Each cell of the matrix is either a rock, denoted by a dot ., or an oil layer represented by a digit from 0 to 9. The digit indicates the number of oil units stored in that cell.

You are allowed to choose a set of columns from the matrix to extract oil. An oil cell is extracted if it is 4-connected (i.e. connected via up, down, left, right moves through oil cells only) to at least one oil cell in one of the chosen columns. In other words, if an oil cell lies in the same connected component (through oil cells) as an oil cell in a chosen column then the entire component is extracted and you obtain the sum of oil units contained in that component.

For each i = 1, 2, …, m, compute the maximum total oil units that can be obtained if you choose exactly i columns.

All formulas are given in LaTeX format. For example, the connectivity is defined as: two cells are adjacent if they share a edge, and the extraction condition is that for a component C, if
\(C \cap S \neq \emptyset\) where \(S\) is the set of chosen columns, then the sum of oil in C is collected.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ small) indicating the number of rows and columns, respectively.

Then follow n lines, each containing a string of length m. Each character is either a dot . (representing rock) or a digit (from 0 to 9, indicating an oil layer with that many units).

outputFormat

Output m integers separated by spaces. The i-th integer represents the maximum total oil units that can be collected if exactly i columns are chosen.

sample

3 5
1.2.3
.4.5.
6.7.8

11 20 27 31 36