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.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
char a[maxn], b[maxn];
int n, m, k;
int g[maxn][maxn][maxn];
int Ne[maxn], to[2][maxn];
void kmp() {
  int p = 0;
  Ne[1] = 0;
  for (int i = 2; i <= m; i++) {
    while (p && b[p + 1] != b[i]) p = Ne[p];
    if (b[p + 1] == b[i]) {
      p++;
      Ne[i] = p;
    }
  }
}
int main() {
  cin >> n >> m;
  scanf("%s", a + 1);
  scanf("%s", b + 1);
  kmp();
  k = n - m + 1;
  memset(g, 0x3f, sizeof(g));
  g[0][0][0] = 0;
  for (int j = 0; j <= m; j++) {
    int p = j;
    while (p != 0 && b[p + 1] != '0') p = Ne[p];
    if (b[p + 1] == '0')
      to[0][j] = p + 1;
    else
      to[0][j] = 0;
    p = j;
    while (p != 0 && b[p + 1] != '1') p = Ne[p];
    if (b[p + 1] == '1')
      to[1][j] = p + 1;
    else
      to[1][j] = 0;
    printf("(%d,%d)", to[0][j], to[1][j]);
  }
  putchar('\n');
  for (int i = 0; i < n; i++) {
    for (int l = 0; l <= k; l++) {
      for (int j = 0; j <= m; j++) {
        if (g[i][j][l] == g[0][0][1]) continue;
        int fl = (a[i + 1] != '0');
        g[i + 1][to[0][j]][l + to[0][j] / m] =
            min(g[i + 1][to[0][j]][l + to[0][j] / m], g[i][j][l] + fl);
        fl = (a[i + 1] != '1');
        g[i + 1][to[1][j]][l + to[1][j] / m] =
            min(g[i + 1][to[1][j]][l + to[1][j] / m], g[i][j][l] + fl);
      }
    }
  }
  for (int i = 0; i <= k; i++) {
    int ans = g[0][0][1];
    for (int j = 0; j <= m; j++) ans = min(ans, g[n][j][i]);
    if (ans == g[0][0][1]) ans = -1;
    printf("%d ", ans);
  }
  return 0;
}
