#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
pii operator+(const pii &a, const pii &b) { return {a.first + b.first, a.second + b.second}; }
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N, M;
vvi A;
vi votes;
int vr; // votes required
vi trans, transR;
struct node
{
bool state;
node *par = nullptr;
node *next[2] = {nullptr, nullptr};
vpii result;
};
void addRes(node *n, pii res)
{
for (int i = 0; i < 2; ++i)
if (n->result[i] < res)
swap(n->result[i], res);
}
struct Trie
{
vector<vector<node *>> layers;
node *root;
void init()
{
layers.resize(M + 1);
root = new node();
root->result.assign(2, {-1, -1});
layers[0].push_back(root);
}
void insert(int v, pii id)
{
insert(v, id, 0, root);
}
void insert(int v, pii id, int idx, node *n)
{
if (idx == M)
{
addRes(n, id);
return;
}
int st = (v >> idx) & 1;
if (n->next[st] == nullptr)
{
n->next[st] = new node();
n->next[st]->par = n;
n->next[st]->state = st;
n->next[st]->result.assign(2, {-1, -1});
layers[idx + 1].push_back(n->next[st]);
}
insert(v, id, idx + 1, n->next[st]);
}
node *query(int v) { return query(v, 0, root); }
node *query(int v, int idx, node *n)
{
if (n == nullptr)
return nullptr;
if (idx == M)
return n;
int st = (v >> idx) & 1;
return query(v, idx + 1, n->next[st]);
}
};
Trie Tid; // Tid
Trie Tma; // matching
const pii add1 = {1, 0};
void cleanuplayer(int idx)
{
for (node *n : Tma.layers[M - idx])
n->result.assign(2, {-1, -1});
}
void dfs(node *nid, int idx)
{
// idx := layer in tid
// M - idx := corespoding layer in Tma
if (idx == M)
{
nid->result = Tma.layers[M - idx][0]->result;
}
else
{
for (int i = 0; i < 2; ++i)
{
if (nid->next[i] == nullptr)
continue;
for (node *n : Tma.layers[M - idx])
{
for (pii p : n->result)
{
if (p.first == -1)
continue;
if (votes[idx] - i - n->state >= vr)
addRes(n->par, p + add1);
else
addRes(n->par, p);
}
}
dfs(nid->next[i], idx + 1);
cleanuplayer(idx + 1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
vr = N / 2;
A.assign(N, vi(M));
votes.assign(M, 0);
trans.assign(N, 0);
transR.assign(N, 0);
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
cin >> A[i][j];
votes[j] += A[i][j];
trans[i] |= (A[i][j]) ? (1 << j) : 0;
transR[i] |= (A[i][j]) ? (1 << (M - 1 - j)) : 0;
}
}
Tid.init();
Tma.init();
for (int i = 0; i < N; ++i)
Tid.insert(trans[i], {-1, -1}), Tma.insert(transR[i], {0, i});
dfs(Tid.root, 0);
for (int i = 0; i < N; ++i)
{
node *tmp = Tid.query(trans[i]);
if (tmp->result[0].second != i)
cout << tmp->result[0].first << "\n";
else
cout << tmp->result[1].first << "\n";
}
return 0;
}
