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 inf = 1 << 30;
const long long Inf = 1ll << 60ll;
namespace io {
char buf[(1 << 23)], *p1 = buf, *p2 = buf, c;
int f;
template <typename T>
T read() {
  T x = 0;
  f = 0;
  c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 23), stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(c))
    (c == '-') && (f = 1),
        c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 23), stdin),
                          p1 == p2)
                 ? EOF
                 : *p1++);
  while (isdigit(c))
    x = x * 10 + (c & 15),
    c = (p1 == p2 &&
                 (p2 = (p1 = buf) + fread(buf, 1, (1 << 23), stdin), p1 == p2)
             ? EOF
             : *p1++);
  return f ? -x : x;
}
}  // namespace io
const int N = 505;
int n, m, kmp[N], dp[N][N][N], nxt[N][N];
char a[N], b[N];
void upt(int& x, int y) { x = min(x, y); }
int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", a + 1);
  scanf("%s", b + 1);
  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;
  }
  memset(dp, 0x3f, sizeof(dp));
  for (int i = 1, j = 0, match = 0; i <= n; ++i) {
    while (j && b[j + 1] != a[i]) j = kmp[j];
    if (a[i] == b[j + 1]) ++j;
    if (j == m) {
      ++match;
      j = kmp[j];
    }
    dp[i][match][j] = 0;
  }
  dp[0][0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < min(m, i); ++j) {
      int t = j, c = b[j + 1] ^ 1;
      while (t && b[t + 1] != c) t = kmp[t];
      if (b[t + 1] == c) ++t;
      nxt[i][j] = t;
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= max(i - m + 1, 0); ++j) {
      for (int k = 0; k < m; ++k) {
        upt(dp[i + 1][j + (k == m - 1)][k == m - 1 ? kmp[m] : k + 1],
            dp[i][j][k] + (a[i + 1] != b[k + 1]));
        upt(dp[i + 1][j][nxt[i][k]], dp[i][j][k] + (a[i + 1] == b[k + 1]));
      }
    }
  }
  for (int i = 0; i <= n - m + 1; ++i) {
    int t = inf;
    for (int j = 0; j < m; ++j) t = min(t, dp[n][i][j]);
    if (t > n)
      printf("-1 ");
    else
      printf("%d ", t);
  }
  return 0;
}
