#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/**
* Stores the top two potential deputies for a given mask to ensure
* we can always pick one that isn't the current chairperson.
*/
struct BestDeputies {
int id1 = -1, id2 = -1;
void update(int new_id, const vector<int>& popcounts) {
if (new_id == -1) return;
if (new_id == id1) return;
if (id1 == -1 || popcounts[new_id] > popcounts[id1]) {
id2 = id1;
id1 = new_id;
} else if (id2 == -1 || popcounts[new_id] > popcounts[id2]) {
id2 = new_id;
}
}
};
int main() {
// Fast I/O is essential for N = 300,000
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
if (!(cin >> N >> M)) return 0;
vector<int> A(N);
vector<int> col_sum(M, 0);
vector<int> member_zeros(N, 0);
for (int i = 0; i < N; ++i) {
string s; cin >> s;
for (int j = 0; j < M; ++j) {
if (s[j] == '1') {
A[i] |= (1 << j);
col_sum[j]++;
}
}
// A member's "Safe Mask" is the inverse of their votes (where they vote 0)
member_zeros[i] = __builtin_popcount(((1 << M) - 1) ^ A[i]);
}
// Step 1: Initialize DP
// dp[mask] will store the best members whose "0-votes" cover this mask.
vector<BestDeputies> dp(1 << M);
vector<int> safe_masks(N);
for (int i = 0; i < N; ++i) {
safe_masks[i] = ((1 << M) - 1) ^ A[i];
dp[safe_masks[i]].update(i, member_zeros);
}
// Step 2: SOS DP (Sum Over Subsets)
// If a deputy's 0-votes cover a large mask, they also cover all its subsets.
// We propagate the "best" members from larger masks down to smaller ones.
for (int j = 0; j < M; ++j) {
for (int mask = (1 << M) - 1; mask >= 0; --mask) {
if (mask & (1 << j)) {
int subset = mask ^ (1 << j);
dp[subset].update(dp[mask].id1, member_zeros);
dp[subset].update(dp[mask].id2, member_zeros);
}
}
}
// Step 3: Solve for each Chairperson
for (int i = 0; i < N; ++i) {
int guaranteed = 0;
int critical_mask = 0;
for (int j = 0; j < M; ++j) {
// How many votes does ordinance j have if member i is Chairperson?
int votes_fixed = col_sum[j] - ((A[i] >> j) & 1);
if (votes_fixed >= N / 2 + 1) {
// Already passes even if deputy votes 1
guaranteed++;
} else if (votes_fixed == N / 2) {
// Only passes if deputy votes 0
critical_mask |= (1 << j);
}
}
// Find the best deputy for this critical mask (the one with the most 0s)
BestDeputies best = dp[critical_mask];
int deputy_id = (best.id1 == i) ? best.id2 : best.id1;
if (deputy_id == -1) {
// Fallback (though in JOI N >= 3, a deputy always exists)
cout << guaranteed << "\n";
} else {
// Result = Guaranteed + (Total Critical - Ruined)
// By picking a deputy who is a "subset" of the Safe Mask (complement of Critical),
// we ensure Ruined = 0 for all bits in the critical mask.
int total_critical = __builtin_popcount(critical_mask);
cout << guaranteed + total_critical << "\n";
}
}
return 0;
}
