/**
____ ____ ____ ____ ____ ____
||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);
}
const int maxn = 3e5 + 10, maxm = 21;
int n, m, imp[maxm], cnt[maxm];
bool a[maxn][maxm];
pair < int, int > dp[maxm][(1 << maxm)][2];
int val_mask[maxn], rev_mask[maxn];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 0; j < m; j ++)
cin >> a[i][j], cnt[j] += a[i][j];
for (int mask = 0; mask < (1 << m); mask ++)
for (int i = 0; i < m; i ++)
dp[i][mask][0] = dp[i][mask][1] = {-1, -1};
for (int i = 1; i <= n; i ++)
{
for (int j = 0; j < m; j ++)
{
val_mask[i] = (val_mask[i] + (1 << j) * a[i][j]);
rev_mask[i] = (rev_mask[i] + (1 << j) * (1 - a[i][j]));
///cout << "mask " << rev_mask[i] << endl;
}
for (int mask = 0; mask < (1 << m); mask ++)
{
if ((mask & rev_mask[i]) == mask)
{
int val = __builtin_popcount(mask);
if (dp[0][mask][0].second == i)
{
dp[0][mask][0].first = max(dp[0][mask][0].first, val);
}
else if (dp[0][mask][1].second == i)
{
dp[0][mask][1].first = max(dp[0][mask][1].first, val);
if (dp[0][mask][0].first < dp[0][mask][1].first)
swap(dp[0][mask][0], dp[0][mask][1]);
}
else if (val > dp[0][mask][0].first)
{
dp[0][mask][1] = dp[0][mask][0];
dp[0][mask][0] = {val, i};
}
else if (val > dp[0][mask][1].first)
{
dp[0][mask][1] = {val, i};
}
}
}
/**int val = __builtin_popcount(rev_mask[i]);
if (dp[0][rev_mask[i]][0].second == i)
{
dp[0][rev_mask[i]][0].first = max(dp[0][rev_mask[i]][0].first, val);
}
else if (dp[0][rev_mask[i]][1].second == i)
{
dp[0][rev_mask[i]][1].first = max(dp[0][rev_mask[i]][1].first, val);
if (dp[0][rev_mask[i]][0].first < dp[0][rev_mask[i]][1].first)
swap(dp[0][rev_mask[i]][0], dp[0][rev_mask[i]][1]);
}
else if (val > dp[0][rev_mask[i]][0].first)
{
dp[0][rev_mask[i]][1] = dp[0][rev_mask[i]][0];
dp[0][rev_mask[i]][0] = {val, i};
}
else if (val > dp[0][rev_mask[i]][1].first)
{
dp[0][rev_mask[i]][1] = {val, i};
}*/
}
for (int i = 1; i <= m; i ++)
for (int mask = 0; mask < (1 << m); mask ++)
{
dp[i][mask][0] = dp[i - 1][mask][0];
dp[i][mask][1] = dp[i - 1][mask][1];
if ((mask & (1 << (i - 1))) > 0)
{
int new_mask = (mask ^ (1 << (i - 1)));
int val = dp[i - 1][new_mask][0].first, idx = dp[i - 1][new_mask][0].second;
if (dp[i][mask][0].second == idx)
{
if (val > dp[i][mask][0].first)
dp[i][mask][0].first = val;
}
else if (dp[i][mask][1].second == idx)
{
if (val > dp[i][mask][1].first)
dp[i][mask][1].first = val;
if (dp[i][mask][0].first < dp[i][mask][1].first)
swap(dp[i][mask][0], dp[i][mask][1]);
}
else if (val > dp[i][mask][0].first)
{
dp[i][mask][1] = dp[i][mask][0];
dp[i][mask][0] = {val, idx};
}
else if (val > dp[i][mask][1].first)
{
dp[i][mask][1] = {val, idx};
}
val = dp[i - 1][new_mask][1].first;
idx = dp[i - 1][new_mask][1].second;
if (dp[i][mask][0].second == idx)
{
if (val > dp[i][mask][0].first)
dp[i][mask][0].first = val;
}
else if (dp[i][mask][1].second == idx)
{
if (val > dp[i][mask][1].first)
dp[i][mask][1].first = val;
if (dp[i][mask][0].first < dp[i][mask][1].first)
swap(dp[i][mask][0], dp[i][mask][1]);
}
else if (val > dp[i][mask][0].first)
{
dp[i][mask][1] = dp[i][mask][0];
dp[i][mask][0] = {val, idx};
}
else if (val > dp[i][mask][1].first)
{
dp[i][mask][1] = {val, idx};
}
}
/// cout << "state " << i << " " << mask << " " << dp[i][mask][0] << " " << dp[i][mask][1] << endl;
}
for (int i = 1; i <= n; i ++)
{
int two = 0, one = 0, zero = 0;
for (int j = 0; j < m; j ++)
{
if (cnt[j] >= n / 2 + 2)
two |= (1 << j);
else if (cnt[j] >= n / 2 + 1)
one |= (1 << j);
else if (cnt[j] >= n / 2)
zero |= (1 << j);
}
int mask = 0, rev = 0;
for (int j = m - 1; j >= 0; j --)
{
mask = mask * 2 + (a[i][j]);
rev = rev * 2 + (1 - a[i][j]);
}
int ONE = two | (one & (rev));
int ZERO = (one & (mask)) | (zero & (rev));
/**cout << i << " : " << ONE << " : " << ZERO << endl;
for (int bit = 0; bit < m; bit ++)
if ((ZERO & (1 << bit)) > 0)
cout << 1 << " ";
else
cout << 0 << " ";
cout << endl;*/
int best = dp[m][ZERO][0].first;
int val = __builtin_popcount(ZERO & rev_mask[i]);
if (val == best)
best = dp[m][ZERO][1].first;
///cout << i << " : " << val << " " << best << endl;
cout << __builtin_popcount(ONE) + best << endl;
continue;
int ans = 0;
for (int p = 1; p <= n; p ++)
{
if (p == i)
continue;
///cout << "here " << p << " " << ((rev_mask[p])) << endl;
int cur = __builtin_popcount((rev_mask[p]) & ZERO);
/**cout << "step " << p << endl;
for (int bit = 0; bit < m; bit ++)
if ((rev_mask[p] & (1 << bit)) > 0)
cout << 1 << " ";
else
cout << 0 << " ";
cout << endl;*/
if (cur > __builtin_popcount(ans))
ans = ((rev_mask[p]) & ZERO);
///ans = max(ans, __builtin_popcount((~val_mask[p]) & zero));
}
ans |= ONE;
cout << __builtin_popcount(ans) << endl;
}
}
int main()
{
///speed();
solve();
return 0;
}
