#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
const int MAXN = 5e2 + 10;
const int MOD = (int)1e9 + 7;
void clear() {}
void precalc() {}
int prefix[MAXN];
int dp[2][MAXN][MAXN];
void solve() {
  int n, m;
  cin >> n >> m;
  string a, b;
  cin >> a >> b;
  for (int i = 1; i < b.size(); ++i) {
    int v = prefix[i - 1];
    while (v > 0 && b[v] != b[i]) v = prefix[v - 1];
    if (b[v] == b[i]) v++;
    prefix[i] = v;
  }
  int k = n - m + 1;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= m; j++) {
      dp[0][j][i] = (int)1e9;
    }
  }
  dp[0][0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= m; j++) {
      for (int c = 0; c <= k; ++c) {
        dp[1][j][c] = (int)1e9;
      }
    }
    for (char l = '0'; l <= '1'; ++l) {
      int cost = l == a[i] ? 0 : 1;
      for (int j = 0; j <= m; j++) {
        int new_j = j;
        if (new_j == m) new_j = prefix[new_j - 1];
        while (new_j && b[new_j] != l) new_j = prefix[new_j - 1];
        if (b[new_j] == l) new_j++;
        int delta_k = new_j == m ? 1 : 0;
        for (int c = 0; c + delta_k <= k; c++) {
          dp[1][new_j][c + delta_k] =
              min(dp[1][new_j][c + delta_k], dp[0][j][c] + cost);
        }
      }
    }
    for (int j = 0; j <= m; j++) {
      for (int c = 0; c <= k; ++c) {
        dp[0][j][c] = dp[1][j][c];
      }
    }
  }
  for (int i = 0; i <= k; ++i) {
    int min_cost = (int)1e9;
    for (int j = 0; j <= m; j++) {
      min_cost = min(min_cost, dp[0][j][i]);
    }
    cout << (min_cost == (int)1e9 ? -1 : min_cost) << ' ';
  }
}
void multisolve() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  precalc();
  solve();
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
const int MAXN = 5e2 + 10;
const int MOD = (int)1e9 + 7;
void clear() {}
void precalc() {}
int prefix[MAXN];
int dp[2][MAXN][MAXN];
void solve() {
  int n, m;
  cin >> n >> m;
  string a, b;
  cin >> a >> b;
  for (int i = 1; i < b.size(); ++i) {
    int v = prefix[i - 1];
    while (v > 0 && b[v] != b[i]) v = prefix[v - 1];
    if (b[v] == b[i]) v++;
    prefix[i] = v;
  }
  int k = n - m + 1;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= m; j++) {
      dp[0][j][i] = (int)1e9;
    }
  }
  dp[0][0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= m; j++) {
      for (int c = 0; c <= k; ++c) {
        dp[1][j][c] = (int)1e9;
      }
    }
    for (char l = '0'; l <= '1'; ++l) {
      int cost = l == a[i] ? 0 : 1;
      for (int j = 0; j <= m; j++) {
        int new_j = j;
        if (new_j == m) new_j = prefix[new_j - 1];
        while (new_j && b[new_j] != l) new_j = prefix[new_j - 1];
        if (b[new_j] == l) new_j++;
        int delta_k = new_j == m ? 1 : 0;
        for (int c = 0; c + delta_k <= k; c++) {
          dp[1][new_j][c + delta_k] =
              min(dp[1][new_j][c + delta_k], dp[0][j][c] + cost);
        }
      }
    }
    for (int j = 0; j <= m; j++) {
      for (int c = 0; c <= k; ++c) {
        dp[0][j][c] = dp[1][j][c];
      }
    }
  }
  for (int i = 0; i <= k; ++i) {
    int min_cost = (int)1e9;
    for (int j = 0; j <= m; j++) {
      min_cost = min(min_cost, dp[0][j][i]);
    }
    cout << (min_cost == (int)1e9 ? -1 : min_cost) << ' ';
  }
}
void multisolve() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  precalc();
  solve();
  return 0;
}

```