#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = 2e3 + 5;
int r, c, grid[mxN][mxN], par[mxN * mxN + 2 * mxN], sum[mxN * mxN + 2 * mxN], col[mxN], rem[mxN][mxN], le[mxN], ri[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;
le[v] = min(le[v], le[u]);
ri[v] = max(ri[v], ri[u]);
sum[v] += sum[u];
par[u] = v;
}
int cost(int i, int j){
return col[j] + rem[i][j];
}
void f(int i, int j, int optl, int optr){
if(i > j) return;
int mid = (i + j) / 2;
pair<int, int> x = {-1, 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];
le[i * c + j] = ri[i * c + j] = j;
tot += grid[i][j];
}
}
}
vector<tuple<int, int, int>> bucket; // l, r, sum
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));
if(grid[i][j] != -1 && find(i * c + j) == (i * c + j)){
bucket.push_back({le[i * c + j], ri[i * c + j], sum[i * c + j]});
}
}
for(auto it : component[j]){
col[j] += sum[it];
}
}
for(auto [l, r, sum] : bucket){
rem[l][l] -= sum;
rem[l][r+1] += sum;
rem[r+1][l] += sum;
rem[r+1][r+1] -= sum;
}
for(int i = 0; i < c; i++){
for(int j = 0; j < c; j++){
rem[i][j] += (i ? rem[i-1][j] : 0)
+ (j ? rem[i][j-1] : 0)
- (i && j ? rem[i-1][j-1] : 0);
}
}
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;
}
}
return 0;
}
