#include <bits/stdc++.h>
#define ll long long
const ll inf = 1e19 + 7;
using namespace std;
ll r, c, n;
vector<string> grid;
vector<pair<ll, ll>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<bool>> vis;
vector<tuple<ll, ll, ll>> ranges;
vector<ll> pref;
bool lol(ll i, ll j) {
return (i >= 1 && j >= 1 && i <= r && j <= c && !vis[i][j] &&
grid[i][j - 1] != '.');
}
ll lf, ri, sum = 0;
void dfs(ll i, ll j) {
lf = min(lf, j);
ri = max(ri, j);
vis[i][j] = 1;
sum += (grid[i][j - 1] - '0');
for (auto [x, y] : dir) {
if (lol(i + x, j + y))
dfs(i + x, j + y);
}
}
void proc_dp() {
vector<vector<ll>> Ls(c + 2), PS(c + 2);
for (ll i = 1; i <= c; ++i) {
vector<pair<ll, ll>> tmp;
tmp.reserve(ranges.size());
for (auto [L, R, W] : ranges) {
if (R >= i)
tmp.push_back({L, W});
}
sort(tmp.begin(), tmp.end(),
[](const pair<ll, ll> &a, const pair<ll, ll> &b) {
return a.first < b.first;
});
Ls[i].resize(tmp.size());
PS[i].resize(tmp.size());
ll s = 0;
for (size_t t = 0; t < tmp.size(); ++t) {
Ls[i][t] = tmp[t].first;
s += tmp[t].second;
PS[i][t] = s;
}
}
auto sum_leq = [&](const vector<ll> &Lvec, const vector<ll> &pref,
ll x) -> ll {
if (Lvec.empty())
return 0;
auto it = upper_bound(Lvec.begin(), Lvec.end(), x);
if (it == Lvec.begin())
return 0;
size_t idx = size_t(it - Lvec.begin() - 1);
return pref[idx];
};
vector<vector<ll>> dp(c + 1, vector<ll>(c + 1, 0));
for (ll t = 1; t <= c; ++t) {
for (ll i = 1; i <= c; ++i) {
ll best = 0;
ll total_to_i = sum_leq(Ls[i], PS[i], i);
for (ll k = 0; k < i; ++k) {
ll total_to_k = sum_leq(Ls[i], PS[i], k);
ll gain = total_to_i - total_to_k;
best = max(best, dp[t - 1][k] + gain);
}
dp[t][i] = best;
}
}
ll pref_ans = 0;
for (ll t = 1; t <= c; ++t) {
ll best = 0;
for (ll i = 1; i <= c; ++i)
best = max(best, dp[t][i]);
pref_ans = max(pref_ans, best);
cout << pref_ans << "\n";
}
}
int main() {
cin >> r >> c;
grid.resize(r + 1);
vis.resize(r + 1, vector<bool>(c + 1));
for (ll i = 1; i <= r; ++i) {
cin >> grid[i];
}
for (ll i = 1; i <= r; ++i) {
for (ll j = 1; j <= c; ++j) {
if (lol(i, j)) {
lf = inf, ri = -1, sum = 0;
dfs(i, j);
ranges.push_back({lf, ri, sum});
}
}
}
proc_dp();
}
