#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
struct Trie {
  struct Node {
    int son[2] = {-1, -1};
    int x = -1;
  };
  vector<Node> a;
  void Init(int init_cap = 0) {
    a.clear();
    a.emplace_back();
    a.reserve(init_cap + 1);
  }
  void Add(const vector<int>& s, int x) {
    int p = 0;
    for (auto& x : (s)) {
      if (a[p].son[x] < 0) {
        a[p].son[x] = int((a).size());
        a.emplace_back();
      }
      p = a[p].son[x];
    }
    a[p].x = x;
  }
};
char a[505], b[505];
int na, nb;
int nxt[505][2];
void Solve() {
  scanf("%d%d", &na, &nb);
  scanf("%s", a);
  scanf("%s", b);
  Trie tr;
  tr.Init(nb * nb);
  vector<int> tmp;
  for (int i = 0; i <= nb; ++i) {
    tmp.clear();
    for (int j = i - 1; j >= 0; --j) tmp.push_back(b[j] - '0');
    tr.Add(tmp, i);
  }
  tmp.resize(nb + 1);
  for (int i = 0; i <= nb; ++i) {
    for (int c = 0; c <= 1; ++c) {
      tmp[i] = c;
      int p = 0;
      int max_len = 0;
      for (int j = i; j >= 0; --j) {
        if (tr.a[p].son[tmp[j]] < 0) break;
        p = tr.a[p].son[tmp[j]];
        if (tr.a[p].x >= 0) max_len = tr.a[p].x;
      }
      nxt[i][c] = max_len;
    }
    42;
    tmp[i] = b[i] - '0';
  }
  int t = na - nb + 1;
  vector<vector<int>> cur;
  cur.push_back({0});
  for (int i = 0; i < na; ++i) {
    auto pre = move(cur);
    cur.clear();
    for (int j = 0; j <= t && j < int((pre).size()); ++j) {
      for (int k = 0; k < int((pre[j]).size()); ++k) {
        int w = pre[j][k];
        if (w == INF) continue;
        for (int d = 0; d <= 1; ++d) {
          int prefix_len = nxt[k][d];
          int w2 = w + (d != a[i] - '0');
          int j2 = j;
          if (prefix_len == nb) {
            ++j2;
          }
          if (j2 >= int((cur).size())) cur.resize(j2 + 1, {});
          if (prefix_len >= int((cur[j2]).size())) {
            cur[j2].resize(prefix_len + 1, INF);
          }
          cur[j2][prefix_len] = min(cur[j2][prefix_len], w2);
        }
      }
    }
  }
  for (int i = 0; i <= t; ++i) {
    int res = INF;
    if (i < int((cur).size())) {
      for (int j = 0; j < int((cur[i]).size()); ++j) res = min(res, cur[i][j]);
    }
    if (res == INF) res = -1;
    printf("%d ", res);
  }
  printf("\n");
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    Solve();
  }
  return 0;
}

### Prompt

Generate a cpp solution 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 EPS = 1e-12;
const int INF = 1e9 + 10;
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
struct Trie {
  struct Node {
    int son[2] = {-1, -1};
    int x = -1;
  };
  vector<Node> a;
  void Init(int init_cap = 0) {
    a.clear();
    a.emplace_back();
    a.reserve(init_cap + 1);
  }
  void Add(const vector<int>& s, int x) {
    int p = 0;
    for (auto& x : (s)) {
      if (a[p].son[x] < 0) {
        a[p].son[x] = int((a).size());
        a.emplace_back();
      }
      p = a[p].son[x];
    }
    a[p].x = x;
  }
};
char a[505], b[505];
int na, nb;
int nxt[505][2];
void Solve() {
  scanf("%d%d", &na, &nb);
  scanf("%s", a);
  scanf("%s", b);
  Trie tr;
  tr.Init(nb * nb);
  vector<int> tmp;
  for (int i = 0; i <= nb; ++i) {
    tmp.clear();
    for (int j = i - 1; j >= 0; --j) tmp.push_back(b[j] - '0');
    tr.Add(tmp, i);
  }
  tmp.resize(nb + 1);
  for (int i = 0; i <= nb; ++i) {
    for (int c = 0; c <= 1; ++c) {
      tmp[i] = c;
      int p = 0;
      int max_len = 0;
      for (int j = i; j >= 0; --j) {
        if (tr.a[p].son[tmp[j]] < 0) break;
        p = tr.a[p].son[tmp[j]];
        if (tr.a[p].x >= 0) max_len = tr.a[p].x;
      }
      nxt[i][c] = max_len;
    }
    42;
    tmp[i] = b[i] - '0';
  }
  int t = na - nb + 1;
  vector<vector<int>> cur;
  cur.push_back({0});
  for (int i = 0; i < na; ++i) {
    auto pre = move(cur);
    cur.clear();
    for (int j = 0; j <= t && j < int((pre).size()); ++j) {
      for (int k = 0; k < int((pre[j]).size()); ++k) {
        int w = pre[j][k];
        if (w == INF) continue;
        for (int d = 0; d <= 1; ++d) {
          int prefix_len = nxt[k][d];
          int w2 = w + (d != a[i] - '0');
          int j2 = j;
          if (prefix_len == nb) {
            ++j2;
          }
          if (j2 >= int((cur).size())) cur.resize(j2 + 1, {});
          if (prefix_len >= int((cur[j2]).size())) {
            cur[j2].resize(prefix_len + 1, INF);
          }
          cur[j2][prefix_len] = min(cur[j2][prefix_len], w2);
        }
      }
    }
  }
  for (int i = 0; i <= t; ++i) {
    int res = INF;
    if (i < int((cur).size())) {
      for (int j = 0; j < int((cur[i]).size()); ++j) res = min(res, cur[i][j]);
    }
    if (res == INF) res = -1;
    printf("%d ", res);
  }
  printf("\n");
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    Solve();
  }
  return 0;
}

```