#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
const int N = 2000 + 2;
int a[N][N];
int n, m, cost[N][N];
int dp[N][N];
struct DSU{
int root, size, l, r, cost;
};
DSU dsu[N * N];
int h[N];
bool mark[N * N];
int getid(int x, int y)
{
return (x - 1) * m + y;
}
int findset(int u)
{
return u == dsu[u].root ? u : dsu[u].root = findset(dsu[u].root);
}
void Union(int u, int v)
{
u = findset(u), v = findset(v);
if (u == v) return ;
if (dsu[u].size < dsu[v].size) swap(u, v);
dsu[u].size += dsu[v].size;
dsu[v].root = u;
dsu[u].l = min(dsu[u].l, dsu[v].l);
dsu[u].r = max(dsu[u].r, dsu[v].r);
dsu[u].cost += dsu[v].cost;
}
void DAC(int l, int r, int L, int R, int c)
{
int mid = (l + r) >> 1;
int costbest = -1, savebest = -1;
forw(i, L, min(mid, R))
{
int costi = cost[i][mid] + dp[i - 1][c - 1];
if (costi > costbest)
costbest = costi, savebest = i;
}
dp[mid][c] = costbest;
if (l == r)
return ;
DAC(l, mid, L, savebest, c);
DAC(mid + 1, r, savebest, R, c);
}
void solve()
{
cin >> n >> m;
forw(i, 1, n) forw(j, 1, m)
{
char val; cin >> val;
a[i][j] = (val == '.' ? -1 : val - '0');
}
forw(i, 1, n) forw(j, 1, m)
{
if (a[i][j] < 0) continue;
int r1 = getid(i, j);
dsu[r1] = {r1, 1, j, j, a[i][j]};
if (i > 1 && a[i - 1][j] >= 0)
Union(r1, getid(i - 1, j));
if (j > 1 && a[i][j - 1] >= 0)
Union(r1, getid(i, j - 1));
}
forw(i, 1, n) forw(j, 1, m)
if (a[i][j] >= 0 && !mark[findset(getid(i, j))])
{
int r1 = findset(getid(i, j));
mark[r1] = 1;
forw(z, dsu[r1].l, dsu[r1].r)
cost[z][dsu[r1].r] += dsu[r1].cost;
}
forw(i, 1, m) forw(j, 1, i)
cost[j][i] += cost[j][i - 1];
forw(i, 1, m){
DAC(i, m, i, m, i);
cout << dp[m][i] << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("test.inp","r",stdin);
// freopen("test.out","w",stdout);
//time_t TIME_TU=clock();
int t=1;
// cin>>t;
while(t--)
solve();
//time_t TIME_TV=clock();
//cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
return 0;
}
