#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e3 + 5;
const int inf = 1e18;
int r, c, grid[mxN][mxN], par[mxN * mxN + 2 * mxN], sum[mxN * mxN + 2 * mxN], col[mxN], mx = 0, tot = 0;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
unordered_set<int> component[mxN];
vector<int> dp_prev, dp_cur;
int find(int u){
return par[u] = (par[u] == u ? u : find(par[u]));
}
void unite(int u, int v){
u = find(u), v = find(v);
if(u == v) return;
sum[v] += sum[u];
par[u] = v;
}
int cost(int i, int j){
int res = col[j];
if(component[i].size() < component[j].size()){
for(auto it : component[i]){
if(component[j].find(it) != component[j].end()) res -= sum[it];
}
}else{
for(auto it : component[j]){
if(component[i].find(it) != component[i].end()) res -= sum[it];
}
}
return res;
}
void f(int i, int j, int optl, int optr){
if(i > j) return;
int mid = (i + j) / 2;
pair<int, int> x = {-inf, 0};
for(int k = optl; k <= min(mid, optr); ++k){
x = max(x, {dp_prev[k] + cost(k, mid), k});
}
mx = max(mx, x.first);
dp_cur[mid] = x.first;
f(i, mid - 1, optl, x.second);
f(mid + 1, j, x.second, optr);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
cin >> r >> c;
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
char ch; cin >> ch;
if(ch == '.') grid[i][j] = -1;
else grid[i][j] = ch - '0';
if(grid[i][j] != -1){
sum[i * c + j] = grid[i][j];
tot += grid[i][j];
}
cout << grid[i][j] << " ";
}
cout << "\n";
}
for(int i = 0; i < mxN * mxN + 2 * mxN; ++i) par[i] = i;
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
if(grid[i][j] == -1) continue;
for(int k = 0; k < 4; ++k){
int ni = i + dx[k], nj = j + dy[k];
if(ni >= 0 && nj >= 0 && ni < r && nj < c && grid[ni][nj] != -1){
unite(i * c + j, ni * c + nj);
}
}
}
}
for(int j = 0; j < c; ++j){
for(int i = 0; i < r; ++i){
if(grid[i][j] != -1) component[j].insert(find(i * c + j));
}
for(auto it : component[j]){
col[j] += sum[it];
}
}
/*dp_prev.resize(c + 1, 0);
dp_cur.resize(c + 1, 0);
for(int j = 0; j < c; ++j){
mx = max(mx, col[j]);
dp_prev[j] = col[j];
}
cout << mx << "\n";
for(int i = 1; i < c; ++i){
mx = 0;
f(0, c - 1, 0, c - 1);
dp_prev = dp_cur;
cout << mx << "\n";
if(mx == tot){
for(int j = i + 1; j < c; ++j){
cout << mx << "\n";
}
break;
}
}*/
vector<vector<int>> dp(c + 1, vector<int> (c + 1, inf));
vector<int> mx_ans(c + 5, 0);
for(int i = 0; i < c; ++i){
dp[i][0] = 0, dp[i][1] = col[i];
for(int j = 1; j <= c; ++j){
for(int prev = i - 1; prev >= 0; --prev){
dp[i][j] = max(dp[i][j], dp[prev][j - 1] + cost(prev, i));
}
mx_ans[j] = max(mx_ans[j], dp[i][j]);
}
}
for(int i = 1; i <= c; ++i) cout << mx_ans[i] << "\n";
return 0;
}
