#include <bits/stdc++.h>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int N = 505;
char a[N], b[N];
int go[N][2], dp[2][N][N];
int kmp[N];
int n, m;
int main() {
  n = read(), m = read();
  scanf("%s", a + 1);
  for (int i = 1; i <= n; i++) a[i] -= '0';
  scanf("%s", b + 1);
  for (int i = 1; i <= m; i++) b[i] -= '0';
  b[m + 1] = 114;
  for (int i = 2, j = 0; i <= m; i++) {
    while (j && b[i] != b[j + 1]) j = kmp[j];
    if (b[i] == b[j + 1]) j++;
    kmp[i] = j;
  }
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j < 2; j++) {
      int t = i;
      while (t && j != b[t + 1]) t = kmp[t];
      if (j == b[t + 1]) t++;
      go[i][j] = t;
    }
  }
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0][0] = 0;
  int now = 0;
  for (int i = 1; i <= n; i++) {
    now ^= 1;
    memset(dp[now], 0x3f, sizeof(dp[now]));
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= i; k++) {
        for (int t = 0; t < 2; t++) {
          int coef = t != a[i];
          ckmin(dp[now][go[j][t]][k + (go[j][t] == m)],
                dp[now ^ 1][j][k] + coef);
        }
      }
    }
  }
  for (int k = 0; k <= n - m + 1; k++) {
    int t = 1e9;
    for (int j = 0; j <= m; j++) ckmin(t, dp[now][j][k]);
    if (t == 1e9) t = -1;
    print(t, " \n"[k == n - m + 1]);
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int N = 505;
char a[N], b[N];
int go[N][2], dp[2][N][N];
int kmp[N];
int n, m;
int main() {
  n = read(), m = read();
  scanf("%s", a + 1);
  for (int i = 1; i <= n; i++) a[i] -= '0';
  scanf("%s", b + 1);
  for (int i = 1; i <= m; i++) b[i] -= '0';
  b[m + 1] = 114;
  for (int i = 2, j = 0; i <= m; i++) {
    while (j && b[i] != b[j + 1]) j = kmp[j];
    if (b[i] == b[j + 1]) j++;
    kmp[i] = j;
  }
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j < 2; j++) {
      int t = i;
      while (t && j != b[t + 1]) t = kmp[t];
      if (j == b[t + 1]) t++;
      go[i][j] = t;
    }
  }
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0][0] = 0;
  int now = 0;
  for (int i = 1; i <= n; i++) {
    now ^= 1;
    memset(dp[now], 0x3f, sizeof(dp[now]));
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= i; k++) {
        for (int t = 0; t < 2; t++) {
          int coef = t != a[i];
          ckmin(dp[now][go[j][t]][k + (go[j][t] == m)],
                dp[now ^ 1][j][k] + coef);
        }
      }
    }
  }
  for (int k = 0; k <= n - m + 1; k++) {
    int t = 1e9;
    for (int j = 0; j <= m; j++) ckmin(t, dp[now][j][k]);
    if (t == 1e9) t = -1;
    print(t, " \n"[k == n - m + 1]);
  }
  return 0;
}

```