description: The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string a of length n. His favorite nephew has another binary string b of length m (m ≤ n).
  
  Mr. Chanek's nephew loves the non-negative integer k. His nephew wants exactly k occurrences of b as substrings in a. 
  
  However, Mr. Chanek does not know the value of k. So, for each k (0 ≤ k ≤ n - m + 1), find the minimum number of elements in a that have to be changed such that there are exactly k occurrences of b in a.
  
  A string s occurs exactly k times in t if there are exactly k different pairs (p,q) such that we can obtain s by deleting p characters from the beginning and q characters from the end of t.
  
  Input
  
  The first line contains two integers n and m (1 ≤ m ≤ n ≤ 500) — size of the binary string a and b respectively.
  
  The second line contains a binary string a of length n.
  
  The third line contains a binary string b of length m.
  
  Output
  
  Output n - m + 2 integers — the (k+1)-th integer denotes the minimal number of elements in a that have to be changed so there are exactly k occurrences of b as a substring in a.
  
  Example
  
  Input
  
  
  9 3
  100101011
  101
  
  
  Output
  
  
  1 1 0 1 6 -1 -1 -1
  
  Note
  
  For k = 0, to make the string a have no occurrence of 101, you can do one character change as follows.
  
  100101011 → 100100011
  
  For k = 1, you can also change a single character.
  
  100101011 → 100001011
  
  For k = 2, no changes are needed.
solution: #include <bits/stdc++.h>
  #pragma GCC optimize("Ofast")
  #pragma GCC optimize("unroll-loops")
  #pragma GCC target("sse,sse2,sse3,ssse3,abm,mmx,tune=native")
  using namespace std;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  inline void boostIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);
  }
  bool isPrime(int x) {
    if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
    for (int i = 5; i * i <= x; i += 6)
      if (x % i == 0 || x % (i + 2) == 0) return 0;
    return 1;
  }
  long long int gcd(long long int a, long long int b) {
    return b ? gcd(b, a % b) : a;
  }
  long long int lcm(long long int a, long long int b) {
    return a * b / gcd(a, b);
  }
  bool BREAKTIME(long double v) { return 1.0 * clock() >= v * CLOCKS_PER_SEC; }
  int mod = 1e9 + 7;
  int inf = 1e9;
  string A;
  string B;
  int f(string s) {
    string z;
    int ans = 0;
    for (int i = s.size() - 1; i >= 0; --i) {
      z = s[i] + z;
      if (z.size() >= B.size()) break;
      bool flag = 1;
      for (int j = 0; j < z.size(); ++j) {
        if (B[j] != z[j]) flag = 0;
      }
      if (flag) ans = max(ans, (int)z.size());
    }
    return ans;
  }
  int dp[2][505][505] = {};
  void solve() {
    int n, m;
    cin >> n >> m;
    cin >> A;
    cin >> B;
    int K = n - m + 1;
    for (int i = 0; i < (2); ++i) {
      for (int j = 0; j < (505); ++j) {
        for (int k = 0; k < (505); ++k) {
          dp[i][j][k] = inf;
        }
      }
    }
    dp[0][0][0] = 0;
    vector<vector<int>> Go(m, vector<int>(2));
    string pref;
    for (int i = 0; i < (m); ++i) {
      string s = pref;
      s.push_back('0');
      Go[i][0] = f(s);
      s = pref;
      s.push_back('1');
      Go[i][1] = f(s);
      pref.push_back(B[i]);
    }
    for (int i = 0; i < (n); ++i) {
      for (int j = 0; j < B.size(); ++j) {
        for (int k = 0; k <= K; ++k) {
          if (j == 0 && k == 1) {
            int kaka = 1;
          }
          if (dp[0][j][k] == inf) continue;
          for (int w = 0; w <= 1; ++w) {
            int nextJ = Go[j][w];
            int nextK = k;
            if (j == (int)B.size() - 1 && B.back() == (w + '0')) {
              nextK++;
            }
            if (nextK > K) continue;
            dp[1][nextJ][nextK] =
                min(dp[1][nextJ][nextK], dp[0][j][k] + (('0' + w) != A[i]));
          }
        }
      }
      swap(dp[0], dp[1]);
      for (int j = 0; j < (505); ++j) {
        for (int k = 0; k < (505); ++k) {
          dp[1][j][k] = inf;
        }
      }
    }
    for (int k = 0; k <= K; ++k) {
      int ans = inf;
      for (int j = 0; j <= B.size(); ++j) {
        ans = min(ans, dp[0][j][k]);
      }
      if (ans == inf) ans = -1;
      cout << ans << " ";
    }
    cout << '\n';
  }
  int32_t main() {
    boostIO();
    int T;
    T = 1;
    while (T--) {
      solve();
    }
  }
  