NAFTA

Time limit2sMemory limit512 MB

Summary

For each K from 1 to S, drill up to K whole columns to drain every touched oil pool and maximize the collected oil.

Level: Medium6 of 10
Topics: Dynamic programming, Intervals, DFS
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

5 5
...3.
....1
..0.3
489..
.....

Expected output

Example 2
Input
```
3 5
999.1
.....
1.999
```
Expected output
```
54
56
56
56
56
```

Example 3

Input

5 5
.27..
7.063
....7
78...
8...2

Expected output