#include <bits/stdc++.h>
using namespace std;
inline void pisz(int n) { printf("%d\n", n); }
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, -1, 0, 1};
const int drr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dcc[8] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename TT>
ostream& operator<<(ostream& s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, vector<T> t) {
  for (int i = 0; i < ((int)((t).size())); i++) s << t[i] << " ";
  return s;
}
class UnionFind {
 private:
  vector<int> rank, p;

 public:
  UnionFind(int n) {
    for (int i = 0; i < n; i++) p.push_back(i);
    rank.assign(n, 0);
  }
  int findSet(int s) { return (p[s] == s) ? s : (p[s] = findSet(p[s])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (isSameSet(i, j)) return;
    int x = findSet(i), y = findSet(j);
    if (rank[x] > rank[y])
      p[y] = x;
    else {
      p[x] = y;
      if (rank[x] == rank[y]) rank[y]++;
    }
  }
};
bool fcomp(double A, double B) {
  double EPSILON = numeric_limits<double>::epsilon();
  double diff = A - B;
  return fabs(diff) < EPSILON;
}
double x_y(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
const int K = 26;
struct Vertex {
  int next[K];
  bool terminal = false;
  int terminal_idx = -1;
  int p = -1;
  char pch;
  int depth = 0;
  int link = 0;
  int next_terminal = 0;
  Vertex(int p, char ch, int depth) : p(p), pch(ch), depth(depth) {
    for (int i = 0; i < K; i++) next[i] = 0;
  }
};
vector<Vertex> t(1, {-1, '$', 0});
void add_string(std::string const& s, int idx) {
  int v = 0;
  for (char ch : s) {
    int c = ch - '0';
    if (!t[v].next[c]) {
      t[v].next[c] = t.size();
      t.emplace_back(v, ch, t[v].depth + 1);
    }
    v = t[v].next[c];
  }
  t[v].terminal = true;
  t[v].terminal_idx = idx;
}
vector<Vertex> tmp = t;
void push_links() {
  std::queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int v = q.front();
    auto& cur = t[v];
    auto& link = t[cur.link];
    q.pop();
    cur.next_terminal = link.terminal ? cur.link : link.next_terminal;
    for (int c = 0; c < K; c++) {
      if (cur.next[c]) {
        t[cur.next[c]].link = v ? link.next[c] : 0;
        q.push(cur.next[c]);
      } else {
        cur.next[c] = link.next[c];
      }
    }
  }
}
int transition(int idx, char c) { return t[idx].next[c - '0']; }
Vertex const& getInfo(int idx) { return t[idx]; }
short dp[510][510][570];
int n, m;
string s;
short rec(int id, int sid, int lft) {
  if (lft < 0) return 1000;
  if (id == n) {
    if (tmp[sid].terminal) lft--;
    if (lft == 0) return 0;
    return 1000;
  }
  short &ret = dp[id][sid][lft], res = 1000;
  if (ret != -1) return ret;
  int d = s[id] - '0';
  d ^= 1;
  if (tmp[sid].next[s[id] - '0']) {
    int c = lft, u = tmp[sid].next[s[id] - '0'];
    res = min(res, rec(id + 1, tmp[sid].next[s[id] - '0'], c));
    if (s[id] == '0') {
      res = min(res, short(1 + rec(id + 1, transition(sid, '1'), c)));
    } else {
      res = min(res, short(1 + rec(id + 1, transition(sid, '0'), c)));
    }
  } else {
    int c = lft;
    if (tmp[sid].terminal) c = lft - 1;
    res = min(res, rec(id + 1, transition(sid, s[id]), c));
    if (s[id] == '0') {
      res = min(res, short(1 + rec(id + 1, transition(sid, '1'), c)));
    } else {
      res = min(res, short(1 + rec(id + 1, transition(sid, '0'), c)));
    }
  }
  return ret = res;
}
int main() {
  memset(dp, -1, sizeof(dp));
  scanf("%d%d", &n, &m);
  string s2;
  cin >> s >> s2;
  add_string(s2, 0);
  tmp = t;
  push_links();
  for (int i = 0; i < n - m + 2; i++) {
    int ans = rec(0, 0, i);
    if (ans > 900) ans = -1;
    cout << ans << " ";
  }
  return 0;
}

### Prompt

Your task is to create 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;
inline void pisz(int n) { printf("%d\n", n); }
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, -1, 0, 1};
const int drr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dcc[8] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename TT>
ostream& operator<<(ostream& s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, vector<T> t) {
  for (int i = 0; i < ((int)((t).size())); i++) s << t[i] << " ";
  return s;
}
class UnionFind {
 private:
  vector<int> rank, p;

 public:
  UnionFind(int n) {
    for (int i = 0; i < n; i++) p.push_back(i);
    rank.assign(n, 0);
  }
  int findSet(int s) { return (p[s] == s) ? s : (p[s] = findSet(p[s])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (isSameSet(i, j)) return;
    int x = findSet(i), y = findSet(j);
    if (rank[x] > rank[y])
      p[y] = x;
    else {
      p[x] = y;
      if (rank[x] == rank[y]) rank[y]++;
    }
  }
};
bool fcomp(double A, double B) {
  double EPSILON = numeric_limits<double>::epsilon();
  double diff = A - B;
  return fabs(diff) < EPSILON;
}
double x_y(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
const int K = 26;
struct Vertex {
  int next[K];
  bool terminal = false;
  int terminal_idx = -1;
  int p = -1;
  char pch;
  int depth = 0;
  int link = 0;
  int next_terminal = 0;
  Vertex(int p, char ch, int depth) : p(p), pch(ch), depth(depth) {
    for (int i = 0; i < K; i++) next[i] = 0;
  }
};
vector<Vertex> t(1, {-1, '$', 0});
void add_string(std::string const& s, int idx) {
  int v = 0;
  for (char ch : s) {
    int c = ch - '0';
    if (!t[v].next[c]) {
      t[v].next[c] = t.size();
      t.emplace_back(v, ch, t[v].depth + 1);
    }
    v = t[v].next[c];
  }
  t[v].terminal = true;
  t[v].terminal_idx = idx;
}
vector<Vertex> tmp = t;
void push_links() {
  std::queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int v = q.front();
    auto& cur = t[v];
    auto& link = t[cur.link];
    q.pop();
    cur.next_terminal = link.terminal ? cur.link : link.next_terminal;
    for (int c = 0; c < K; c++) {
      if (cur.next[c]) {
        t[cur.next[c]].link = v ? link.next[c] : 0;
        q.push(cur.next[c]);
      } else {
        cur.next[c] = link.next[c];
      }
    }
  }
}
int transition(int idx, char c) { return t[idx].next[c - '0']; }
Vertex const& getInfo(int idx) { return t[idx]; }
short dp[510][510][570];
int n, m;
string s;
short rec(int id, int sid, int lft) {
  if (lft < 0) return 1000;
  if (id == n) {
    if (tmp[sid].terminal) lft--;
    if (lft == 0) return 0;
    return 1000;
  }
  short &ret = dp[id][sid][lft], res = 1000;
  if (ret != -1) return ret;
  int d = s[id] - '0';
  d ^= 1;
  if (tmp[sid].next[s[id] - '0']) {
    int c = lft, u = tmp[sid].next[s[id] - '0'];
    res = min(res, rec(id + 1, tmp[sid].next[s[id] - '0'], c));
    if (s[id] == '0') {
      res = min(res, short(1 + rec(id + 1, transition(sid, '1'), c)));
    } else {
      res = min(res, short(1 + rec(id + 1, transition(sid, '0'), c)));
    }
  } else {
    int c = lft;
    if (tmp[sid].terminal) c = lft - 1;
    res = min(res, rec(id + 1, transition(sid, s[id]), c));
    if (s[id] == '0') {
      res = min(res, short(1 + rec(id + 1, transition(sid, '1'), c)));
    } else {
      res = min(res, short(1 + rec(id + 1, transition(sid, '0'), c)));
    }
  }
  return ret = res;
}
int main() {
  memset(dp, -1, sizeof(dp));
  scanf("%d%d", &n, &m);
  string s2;
  cin >> s >> s2;
  add_string(s2, 0);
  tmp = t;
  push_links();
  for (int i = 0; i < n - m + 2; i++) {
    int ans = rec(0, 0, i);
    if (ans > 900) ans = -1;
    cout << ans << " ";
  }
  return 0;
}

```