/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
int x, y;
cell(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
cell operator + (const cell & c) const
{
cell r;
r.x = x + c.x;
r.y = y + c.y;
return r;
}
};
cell neib[4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const int maxn = 2010;
int n, m, sum[maxn * maxn], used[maxn][maxn];
int lm[maxn * maxn], rm[maxn * maxn], met[maxn * maxn];
char c[maxn][maxn];
void bfs(int i, int j)
{
cell st(i, j);
queue < cell > q;
q.push(st);
while(!q.empty())
{
st = q.front();
q.pop();
for (int i = 0; i < 4; i ++)
{
cell nb = st + neib[i];
if (!used[nb.x][nb.y])
{
used[nb.x][nb.y] = used[st.x][st.y];
q.push(nb);
}
}
}
}
int cost[maxn][maxn], df[maxn], dp[maxn][maxn], row;
void divide(int l, int r, int optl, int optr)
{
if (l > r)
return;
int opt = -1, mid = (l + r) / 2, f = -1e9;
for (int i = optl; i <= min(optr, mid); i ++)
{
if (dp[row - 1][i] + cost[i][mid] > f)
{
f = dp[row - 1][i] + cost[i][mid];
opt = i;
}
}
dp[row][mid] = f;
divide(l, mid - 1, optl, opt);
divide(mid + 1, r, opt, optr);
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
cin >> c[i][j];
if (c[i][j] == '.')
used[i][j] = 1;
}
for (int i = 0; i <= n + 1; i ++)
used[i][0] = used[i][m + 1] = 1;
for (int j = 0; j <= m + 1; j ++)
used[0][j] = used[n + 1][j] = 1;
int cnt = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (!used[i][j])
{
cnt ++;
used[i][j] = cnt;
bfs(i, j);
}
}
for (int i = 1; i <= cnt; i ++)
lm[i] = m + 1, rm[i] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (c[i][j] == '.')
{
used[i][j] = 0;
continue;
}
sum[used[i][j]] += (int)(c[i][j] - '0');
lm[used[i][j]] = min(lm[used[i][j]], j);
rm[used[i][j]] = max(rm[used[i][j]], j);
}
for (int j = 1; j <= m; j ++)
{
int cur = 0;
for (int i = 1; i <= n; i ++)
{
if (!met[used[i][j]])
{
met[used[i][j]] = 1;
df[rm[used[i][j]]] += sum[used[i][j]];
cur += sum[used[i][j]];
}
}
for (int i = 1; i <= n; i ++)
met[used[i][j]] = 0;
for (int j1 = 0; j1 < j; j1 ++)
cost[j1][j] += cur;
int to_rem = cur - df[j];
for (int j1 = j + 1; j1 <= m; j1 ++)
{
cost[j][j1] -= to_rem;
to_rem -= df[j1];
}
for (int j1 = 1; j1 <= m; j1 ++)
df[j1] = 0;
}
for (int j = 1; j <= m; j ++)
{
row = j;
divide(1, n, 0, n);
for (int i = 1; i <= n; i ++)
dp[j][i] = max(dp[j][i], dp[j][i - 1]);
}
for (int j = 1; j <= m; j ++)
cout << dp[j][n] << endl;
}
int main()
{
solve();
return 0;
}
