#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
#define ID(x, y) ((x - 1) * nCol + (y - 1))
const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const int INF = 1e9 + 7;
const int MAX = 2020;
int nRow;
int nCol;
int f[MAX];
int g[MAX];
char a[MAX][MAX];
int pf[MAX][MAX];
int co[MAX][MAX];
int mn[MAX * MAX];
int mx[MAX * MAX];
int sum[MAX * MAX];
int lab[MAX * MAX];
bool used[MAX * MAX];
int findSet(int v) {
return lab[v] < 0 ? v : lab[v] = findSet(lab[v]);
}
bool unionSet(int u, int v) {
u = findSet(u);
v = findSet(v);
if (u == v) return false;
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v]; lab[v] = u;
mx[u] = max(mx[u], mx[v]);
mn[u] = min(mn[u], mn[v]);
sum[u] += sum[v];
return true;
}
void init(void) {
cin >> nRow >> nCol;
for (int i = 1; i <= nRow; ++i) {
for (int j = 1; j <= nCol; ++j)
cin >> a[i][j];
}
for (int i = 1; i <= nRow; ++i) for (int j = 1; j <= nCol; ++j) if (a[i][j] != '.') {
mn[ID(i, j)] = j;
mx[ID(i, j)] = j;
lab[ID(i, j)] = -1;
sum[ID(i, j)] = a[i][j] - '0';
}
for (int i = 1; i <= nRow; ++i) for (int j = 1; j <= nCol; ++j) if (a[i][j] != '.') {
for (int k = 0; k < 4; ++k) {
int x = i + dx[k], y = j + dy[k];
if (x <= 0 || x > nRow) continue;
if (y <= 0 || y > nCol) continue;
if (a[x][y] != '.') unionSet(ID(i, j), ID(x, y));
}
}
for (int j = 1; j <= nCol; ++j) {
for (int i = 1; i <= nRow; ++i) if (a[i][j] != '.') {
int root = findSet(ID(i, j));
if (used[root] == false) {
used[root] = true;
pf[j][mn[root] + 0] += sum[root];
pf[j][mx[root] + 1] -= sum[root];
}
}
for (int k = 1; k <= nCol; ++k) {
pf[j][k] += pf[j][k - 1];
}
for (int i = 1; i <= nRow; ++i) if (a[i][j] != '.') {
int root = findSet(ID(i, j));
used[root] = false;
}
}
for (int i = 1; i <= nCol; ++i) {
for (int j = i; j <= nCol; ++j)
co[i][j] = pf[j][j] - pf[j][i];
}
}
void calc(int l, int r, int optL, int optR) {
if (l > r) return;
int mid = l + r >> 1;
pair<int, int> best(-INF, -1);
for (int k = optL; k <= min(optR, mid - 1); ++k) best = max(best, make_pair(g[k] + co[k][mid], -k));
f[mid] = best.fi; int opt = -best.se;
calc(l, mid - 1, optL, opt);
calc(mid + 1, r, opt, optR);
}
void process(void) {
for (int i = 1; i <= nCol; ++i) {
g[i] = pf[i][i];
f[i] = g[i];
}
cout << *max_element(f + 1, f + 1 + nCol) << '\n';
for (int i = 2; i <= nCol; ++i) {
calc(1, nCol, 1, nCol);
for (int i = 1; i <= nCol; ++i) g[i] = f[i];
cout << *max_element(f + 1, f + 1 + nCol) << '\n';
}
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
init(); process();
return 0;
}
