#include <bits/stdc++.h>
using namespace std;
// Định nghĩa các hằng số và macro
const int MAX_N = 300005;
const int MAX_M = 20;
const int LIMIT = (1 << MAX_M);
int n, m;
int vote[MAX_N]; // Lưu phiếu bầu gốc của từng người
int agree[MAX_M]; // Đếm tổng số phiếu thuận cho mỗi dự luật
// Struct để lưu Top 2 giá trị tốt nhất (tránh trường hợp trùng ID với chủ tịch)
struct Top2 {
int v1, id1; // Best: giá trị và ID
int v2, id2; // Second best: giá trị và ID
Top2() {
v1 = -1; id1 = -1;
v2 = -1; id2 = -1;
}
// Hàm cập nhật một giá trị mới vào Top 2
void update(int val, int id) {
if (id == -1) return;
// Nếu trùng ID với người đang giữ top 1, chỉ cập nhật giá trị nếu tốt hơn
if (id == id1) {
v1 = max(v1, val);
return;
}
// Nếu trùng ID với người đang giữ top 2
if (id == id2) {
v2 = max(v2, val);
// Sau khi cập nhật top 2, cần kiểm tra xem có đổi chỗ với top 1 không
if (v2 > v1) {
swap(v1, v2);
swap(id1, id2);
}
return;
}
// Trường hợp ID mới hoàn toàn
if (val > v1) {
v2 = v1; id2 = id1;
v1 = val; id1 = id;
} else if (val > v2) {
v2 = val; id2 = id;
}
}
// Hàm trộn (merge) 2 struct Top2 (dùng cho DP)
void merge(const Top2& other) {
if (other.id1 != -1) update(other.v1, other.id1);
if (other.id2 != -1) update(other.v2, other.id2);
}
};
Top2 cover[LIMIT]; // Giai đoạn 1: Lưu ai bao phủ mask này
Top2 best[LIMIT]; // Giai đoạn 2: Lưu kết quả tối ưu cho truy vấn
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n >> m)) return 0;
// 1. Nhập liệu
for (int i = 1; i <= n; i++) {
int mask = 0;
for (int j = 0; j < m; j++) {
int t; cin >> t;
if (t == 1) mask |= (1 << j); // SỬA LỖI: Chỉ bật bit nếu t=1
agree[j] += t;
}
vote[i] = mask;
}
// 2. Giai đoạn 1: SOS DP (Superset -> Subset)
// Mục tiêu: cover[mask] lưu ID những người mà phiếu đảo (inv_vote) của họ LÀ SUPERSET của mask.
// Tức là nếu mask có bit 1 ở đâu, thì người đó cũng có bit 1 ở đó (trong inv_vote).
// Khởi tạo cơ bản
for (int i = 1; i <= n; i++) {
// Lấy phiếu đảo ngược: bit 1 nghĩa là người đó bầu 0 (hợp với danger)
int inv = (~vote[i]) & ((1 << m) - 1);
// Người i bao phủ chính xác cái inv mask của họ
cover[inv].update(0, i); // Giá trị 0 ở đây không quan trọng, ta chỉ cần ID
}
// Lan truyền từ cha xuống con
for (int i = 0; i < m; i++) {
for (int mask = (1 << m) - 1; mask >= 0; mask--) {
if ((mask >> i) & 1) {
// Nếu mask có bit i bật (1...1), nó có thể nhận update từ mask cha (mask này cũng tồn tại trong tập con của người sở hữu mask)
// Nhưng logic đúng ở đây là: Nếu tôi có mask "111", tôi cũng có "011".
// Tức là người sở hữu "111" cũng sở hữu "011".
// "111" (mask) -> "011" (sub).
// Vậy sub nhận từ mask.
int sub = mask ^ (1 << i);
cover[sub].merge(cover[mask]);
}
}
}
// 3. Giai đoạn 2: SOS DP (Subset -> Superset)
// Mục tiêu: best[mask] lưu max popcount của một mask HỢP LỆ (có trong cover) nằm bên trong mask truy vấn.
// Khởi tạo cơ bản từ mảng cover
for (int mask = 0; mask < (1 << m); mask++) {
if (cover[mask].id1 != -1) {
int p_count = __builtin_popcount(mask);
best[mask].update(p_count, cover[mask].id1);
if (cover[mask].id2 != -1) {
best[mask].update(p_count, cover[mask].id2);
}
}
}
// Lan truyền từ con lên cha (để tìm max trong vùng)
for (int i = 0; i < m; i++) {
for (int mask = 0; mask < (1 << m); mask++) {
if ((mask >> i) & 1) {
int sub = mask ^ (1 << i);
best[mask].merge(best[sub]);
}
}
}
// 4. Trả lời truy vấn
int threshold = n / 2;
for (int i = 1; i <= n; i++) {
int safe_count = 0;
int danger_mask = 0;
for (int j = 0; j < m; j++) {
// Tính số phiếu còn lại nếu bỏ phiếu của i đi
int total_remain = agree[j] - ((vote[i] >> j) & 1);
if (total_remain >= threshold + 1) {
safe_count++; // Chắc chắn đậu
} else if (total_remain == threshold) {
danger_mask |= (1 << j); // Cần người khác bầu 0 vào vị trí này
}
}
// Tìm người j tốt nhất trong danger_mask
// Ta cần người mà inv_vote của họ giao với danger_mask có nhiều bit 1 nhất.
// Mảng best[danger_mask] đã lưu chính xác điều này.
int bonus = 0;
Top2 res = best[danger_mask];
if (res.id1 != -1) {
if (res.id1 != i) {
bonus = res.v1;
} else {
// Nếu người tốt nhất là chính mình, lấy người nhì
if (res.id2 != -1) {
bonus = res.v2;
} else {
bonus = 0;
}
}
}
cout << safe_count + bonus << "\n";
}
return 0;
}
