#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
void solve() {
  int n, m;
  cin >> n >> m;
  vvi dp(m, vi(n - m + 2, -1));
  string a, b;
  cin >> a >> b;
  dp[0][0] = 0;
  vector<array<int, 2>> nxt(m + 1, array<int, 2>{0, 0});
  vi p(m, 0);
  {
    for (int i = 1; i < m; ++i) {
      p[i] = p[i - 1];
      while (p[i] && b[p[i]] != b[i]) p[i] = p[p[i] - 1];
      if (b[p[i]] == b[i]) p[i]++;
    }
    for (int i = 0; i < (m + 1); ++i) {
      nxt[i][0] = nxt[i][1] = 0;
      if (b[i] == '1') {
        nxt[i][1] = i + 1;
        if (i) nxt[i][0] = nxt[p[i - 1]][0];
      } else {
        nxt[i][0] = i + 1;
        if (i) nxt[i][1] = nxt[p[i - 1]][1];
      }
    }
  }
  for (int i = 0; i < (n); ++i) {
    vvi dp2(m, vi(n - m + 2, -1));
    for (int pref = 0; pref < (m); ++pref) {
      for (int occs = 0; occs < (n - m + 2); ++occs) {
        for (int x = 0; x < (2); ++x) {
          int value = dp[pref][occs];
          if (value == -1) continue;
          if (x != (a[i] - '0')) value++;
          int pref2 = nxt[pref][x];
          int occs2 = occs;
          if (pref2 == m) {
            occs2++;
            pref2 = p[m - 1];
          }
          if (occs2 > n - m + 1) continue;
          if (dp2[pref2][occs2] == -1 || dp2[pref2][occs2] > value) {
            dp2[pref2][occs2] = value;
          }
        }
      }
    }
    swap(dp, dp2);
  }
  for (int i = 0; i < (n - m + 2); ++i) {
    int mn = -1;
    for (int j = 0; j < (m); ++j) {
      if (dp[j][i] == -1) continue;
      if (mn == -1 || dp[j][i] < mn) mn = dp[j][i];
    }
    cout << mn << ' ';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 0; i < (t); ++i) {
    solve();
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
using ll = long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
void solve() {
  int n, m;
  cin >> n >> m;
  vvi dp(m, vi(n - m + 2, -1));
  string a, b;
  cin >> a >> b;
  dp[0][0] = 0;
  vector<array<int, 2>> nxt(m + 1, array<int, 2>{0, 0});
  vi p(m, 0);
  {
    for (int i = 1; i < m; ++i) {
      p[i] = p[i - 1];
      while (p[i] && b[p[i]] != b[i]) p[i] = p[p[i] - 1];
      if (b[p[i]] == b[i]) p[i]++;
    }
    for (int i = 0; i < (m + 1); ++i) {
      nxt[i][0] = nxt[i][1] = 0;
      if (b[i] == '1') {
        nxt[i][1] = i + 1;
        if (i) nxt[i][0] = nxt[p[i - 1]][0];
      } else {
        nxt[i][0] = i + 1;
        if (i) nxt[i][1] = nxt[p[i - 1]][1];
      }
    }
  }
  for (int i = 0; i < (n); ++i) {
    vvi dp2(m, vi(n - m + 2, -1));
    for (int pref = 0; pref < (m); ++pref) {
      for (int occs = 0; occs < (n - m + 2); ++occs) {
        for (int x = 0; x < (2); ++x) {
          int value = dp[pref][occs];
          if (value == -1) continue;
          if (x != (a[i] - '0')) value++;
          int pref2 = nxt[pref][x];
          int occs2 = occs;
          if (pref2 == m) {
            occs2++;
            pref2 = p[m - 1];
          }
          if (occs2 > n - m + 1) continue;
          if (dp2[pref2][occs2] == -1 || dp2[pref2][occs2] > value) {
            dp2[pref2][occs2] = value;
          }
        }
      }
    }
    swap(dp, dp2);
  }
  for (int i = 0; i < (n - m + 2); ++i) {
    int mn = -1;
    for (int j = 0; j < (m); ++j) {
      if (dp[j][i] == -1) continue;
      if (mn == -1 || dp[j][i] < mn) mn = dp[j][i];
    }
    cout << mn << ' ';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 0; i < (t); ++i) {
    solve();
  }
  return 0;
}

```