/// code take from: https://www.luogu.com.cn/problem/solution/P9333 #include<bits/stdc++.h> using namespace std; const int N=300005; const int bk=(1<<10)-1; int n,m; int a[N][21]; int vl[(1<<10)+5][(1<<10)+5],p; int num[N]; int val[N]; int ans[N]; int cnt[(1<<10)+5]; void insert(int num) { int half=num&bk; int res=num>>10; for(int i=0;i<1024;i++) { vl[i][res]=min(vl[i][res],cnt[half&i]); } } int get(int x) { int half=x&bk; int res=x>>10; int val=1e9+7; for(int i=0;i<1024;i++) { val=min(val,vl[half][i]+cnt[res&i]); } return val; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=0;i<1024;i++) { cnt[i]=__builtin_popcount(i); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; if(a[i][j]) { num[j-1]++; val[i]|=(1<<j-1); } } } m=20; memset(vl,0x3f,sizeof(vl)); insert(val[1]); int mid=n>>1; for(int i=2;i<=n;i++) { int sum=0; for(int j=0;j<m;j++) { if((val[i]>>j)&1)num[j]--; } int tmp=0; for(int j=0;j<m;j++) { if(num[j]>=mid)sum++; if(num[j]==mid)tmp|=(1<<j); } ans[i]=max(ans[i],sum-get(tmp)); for(int j=0;j<m;j++) { if((val[i]>>j)&1)num[j]++; } insert(val[i]); } memset(vl,0x3f,sizeof(vl)); insert(val[n]); for(int i=n-1;i>=1;i--) { int sum=0; for(int j=0;j<m;j++) { if((val[i]>>j)&1)num[j]--; } int tmp=0; for(int j=0;j<m;j++) { if(num[j]>=mid)sum++; if(num[j]==mid)tmp|=(1<<j); } ans[i]=max(ans[i],sum-get(tmp)); for(int j=0;j<m;j++) { if((val[i]>>j)&1)num[j]++; } insert(val[i]); } for(int i=1;i<=n;i++) { cout<<ans[i]<<'\n'; } }