#pragma region template #pragma GCC optimize("Ofast") #include using namespace std; using ll = long long; using ld = long double; using vi = vector; using vll = vector; using pi = pair; using pll = pair; #define overload2(a, b, c, ...) c #define overload3(a, b, c, d, ...) d #define overload4(a, b, c, d, e, ...) e #define overload5(a, b, c, d, e, f, ...) f #define TYPE1(T) template #define TYPE2(T, U) template #define TYPE(...) overload2(__VA_ARGS__, TYPE2, TYPE1)(__VA_ARGS__) #define TYPES1(T) template #define TYPES2(H, T) template #define TYPES(...) overload2(__VA_ARGS__, TYPES2, TYPES1)(__VA_ARGS__) #define REP4(i, s, n, d) for (int i = (s); i < (n); i += (d)) #define REP3(i, s, n) REP4(i, s, n, 1) #define REP2(i, n) REP3(i, 0, n) #define REP1(n) REP2(tomato, n) #define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define RREP4(i, n, s, d) for (int i = (n)-1; i >= (s); i -= (d)) #define RREP3(i, n, s) RREP4(i, n, s, 1) #define RREP2(i, n) RREP3(i, n, 0) #define RREP1(n) RREP2(tomato, n) #define RREP(...) \ overload4(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__) #define FOR4(a, b, c, d, v) for (auto [a, b, c, d] : v) #define FOR3(a, b, c, v) for (auto [a, b, c] : v) #define FOR2(a, b, v) for (auto [a, b] : v) #define FOR1(a, v) for (auto a : v) #define FOR(...) overload5(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define AFOR4(a, b, c, d, v) for (auto &[a, b, c, d] : v) #define AFOR3(a, b, c, v) for (auto &[a, b, c] : v) #define AFOR2(a, b, v) for (auto &[a, b] : v) #define AFOR1(a, v) for (auto &a : v) #define AFOR(...) \ overload5(__VA_ARGS__, AFOR4, AFOR3, AFOR2, AFOR1)(__VA_ARGS__) #define CFOR4(a, b, c, d, v) for (const auto &[a, b, c, d] : v) #define CFOR3(a, b, c, v) for (const auto &[a, b, c] : v) #define CFOR2(a, b, v) for (const auto &[a, b] : v) #define CFOR1(a, v) for (const auto &a : v) #define CFOR(...) \ overload5(__VA_ARGS__, CFOR4, CFOR3, CFOR2, CFOR1)(__VA_ARGS__) #define PFOR(v) \ for (bool f = true; (f ? exchange(f, false) : next_permutation(ALL(v)));) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define SORT(v) sort(ALL(v)) #define RSORT(v) sort(RALL(v)) #define REVERSE(v) reverse(ALL(v)) #define UNIQUE(v) SORT(v), v.erase(unique(ALL(v)), v.end()) #define SZ(v) int(v.size()) #define MAX(v) *max_element(ALL(v)) #define MIN(v) *min_element(ALL(v)) template conditional_t, ll, T> SUM(const vector &v) { return accumulate(ALL(v), conditional_t, ll, T>(0)); } TYPES(T) void input(T &...a) { (cin >> ... >> a); } #define DECLARE(T, ...) \ T __VA_ARGS__; \ input(__VA_ARGS__); #define INT(...) DECLARE(int, __VA_ARGS__) #define STR(...) DECLARE(string, __VA_ARGS__) #define LL(...) DECLARE(long long, __VA_ARGS__) #define CHR(...) DECLARE(char, __VA_ARGS__) #define DBL(...) DECLARE(double, __VA_ARGS__) #define VI(n, v) \ vi v(n); \ cin >> v; #define VLL(n, v) \ vll v(n); \ cin >> v; #define VS(n, s) \ vector s(n); \ cin >> s; TYPE(T) istream &operator>>(istream &is, vector &v) { for (auto &a : v) cin >> a; return is; } TYPE(T) ostream &operator<<(ostream &os, const vector &v) { if (&os == &cerr) os << "["; REP (i, v.size()) { os << v[i]; if (i + 1 < v.size()) os << (&os == &cerr ? "," : " "); } if (&os == &cerr) os << "]"; return os; } TYPE(T, S) istream &operator>>(istream &is, pair &p) { cin >> p.first >> p.second; return is; } #ifdef __DEBUG #include #else #define debug(...) void(0) #endif void print() { cout << '\n'; } TYPES(T, Ts) void print(const T &a, const Ts &...b) { cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } TYPE(T) using pq = priority_queue; TYPE(T) using pqg = priority_queue, greater>; TYPE(T) T pick(queue &que) { assert(que.size()); T a = que.front(); que.pop(); return a; } TYPE(T) T pick(pq &que) { assert(que.size()); T a = que.top(); que.pop(); return a; } TYPE(T) T pick(pqg &que) { assert(que.size()); T a = que.top(); que.pop(); return a; } TYPE(T) T pick(stack &sta) { assert(sta.size()); T a = sta.top(); sta.pop(); return a; } TYPE(T) void clear(T &v) { v = decltype(v)(); } string YES(bool f = true) { return (f ? "YES" : "NO"); } string Yes(bool f = true) { return (f ? "Yes" : "No"); } string yes(bool f = true) { return (f ? "yes" : "no"); } constexpr int INF = 1e9 + 7; constexpr ll LINF = ll(1e18) + 7; constexpr ld EPS = 1e-10; vi iota(int n) { vi a(n); iota(ALL(a), 0); return a; } TYPE(T) vector> query_sort(const vector &v) { vector> res(v.size()); REP (i, v.size()) res[i] = {v[i], i}; SORT(res); return res; } TYPE(T) void add(vector &v, T a = 1) { AFOR (p, v) p += a; } TYPE(T) T rev(T a) { REVERSE(a); return a; } TYPE(T) void fin(T a) { cout << a << '\n'; exit(0); } TYPE(T) bool chmax(T &a, T b) { return (a < b && (a = b, true)); } TYPE(T) bool chmin(T &a, T b) { return (a > b && (a = b, true)); } TYPES(T, Ns) auto make_vector(T x, int n, Ns... ns) { if constexpr (sizeof...(ns) == 0) return vector(n, x); else return vector(n, make_vector(x, ns...)); } bool in(const ll S, const int a) { return (S >> a) & 1; } int popcount(const ll S) { return __builtin_popcountll(S); } int digit(char c) { return (c >= '0' and c <= '9' ? c - '0' : -1); } ll sqrtll(ll a) { for (ll b = sqrt(a); b * b <= a; b++) if (b * b == a) return b; for (ll b = sqrt(a); b >= 0 and b * b >= a; b--) if (b * b == a) return b; return -1; } #pragma endregion template #include #include using namespace atcoder; using mint = modint998244353; namespace atcoder { ostream &operator<<(ostream &os, mint a) { os << a.val(); return os; } istream &operator>>(istream &is, mint &a) { long long b; is >> b; a = b; return is; } } // namespace atcoder template class MintUtility{ vector fact_={MINT::raw(1)}; vector inv_fact_{MINT::raw(1)}; int S=1;//今のサイズ void extend(const int n){ if(npreS;i--)inv_fact_[i-1]=inv_fact_[i]*MINT::raw(i); } public: MINT fact(const int n){ assert(n>=0); extend(n); return fact_[n]; } MINT inv_fact(const int n){ assert(n>=0); extend(n); return inv_fact_[n]; } MINT nCk(const int n,const int k){ if(k<0||n>a)&1; } } #define REP_(i,n) for(int i=0;i<(n);i++) struct BitwiseAnd{ template static void zeta(vector& A){ int n=bitwise::log2(A.size()); REP_(k,n)REP_(S,1< static void mobius(vector& A){ int n=bitwise::log2(A.size()); REP_(k,n)REP_(S,1< static vector convolution(vector A,vector B){ assert(A.size()==B.size()); zeta(A); zeta(B); REP_(i,A.size())A[i]*=B[i]; mobius(A); return A; } }; #undef REP_ #define REP_(i,n) for(int i=0;i<(n);i++) struct BitwiseOr{ template static void zeta(vector& A){ int n=bitwise::log2(A.size()); REP_(k,n)REP_(S,1< static void mobius(vector& A){ int n=bitwise::log2(A.size()); REP_(k,n)REP_(S,1< static vector convolution(vector A,vector B){ assert(A.size()==B.size()); zeta(A); zeta(B); REP_(i,A.size())A[i]*=B[i]; mobius(A); return A; } }; #undef REP_ MintUtility M; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); INT(n, m, k); vector a(n + 1, 0); for (int l = k; l <= n; l++) { a[l] = 1; for (int i = k; i < l; i++) a[l] -= M.nCk(l, i).val() * a[i]; } vector v(1 << n, 0); REP (m) { STR(s); v[std::stoi(s, nullptr, 2)]++; } BitwiseAnd::zeta(v); REP (S, 1 << n) v[S] *= a[popcount(S)]; BitwiseOr::zeta(v); vector ans(m + 1, n); REP (S, 1 << n) chmin(ans[v[S]], popcount(S)); RREP (i, m) chmin(ans[i], ans[i + 1]); REP (i, 1, m + 1) cout << ans[i] << '\n'; }