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 N = 500 + 7, M = 2e3 + 1;
const int MOD = 1e9 + 7;
const int oo = 1e9 + 7;
int n, m, k, t;
int _dp[N][N][N];
int nxt[N][2];
int a[N][2];
void upd(int &a, int b) { a = min(a, b); }
signed main() {
  scanf("%d%d\n", &n, &m);
  char s[n + 1], t[m + 1];
  scanf("%s\n%s", &s, &t);
  for (int i = 1; i <= n; i++) {
    a[i][0] = s[i - 1] - '0';
  }
  for (int i = 1; i <= m; i++) {
    a[i][1] = t[i - 1] - '0';
  }
  k = n - m + 2;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      for (int l = 0; l <= k; l++) {
        _dp[i][j][l] = oo;
      }
    }
  }
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j < 2; j++) {
      nxt[i][j] = 0;
      for (int l = min(i + 1, m); l > 0; l--) {
        if (j != a[l][1]) continue;
        bool ok = 1;
        for (int p = l - 1; p > 0; p--) {
          if (a[i - l + 1 + p][1] != a[p][1]) {
            ok = 0;
            break;
          }
        }
        if (ok) {
          nxt[i][j] = l;
          break;
        }
      }
    }
  }
  int nw = 0;
  for (int l = m - 1; l > 0; l--) {
    if (a[m][1] != a[l][1]) continue;
    bool ok = 1;
    for (int p = l - 1; p > 0; p--) {
      if (a[m - l + 1 + p][1] != a[p][1]) {
        ok = 0;
        break;
      }
    }
    if (ok) {
      nw = l;
      break;
    }
  }
  _dp[0][0][0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= m; j++) {
      for (int l = 0; l <= k; l++) {
        if (_dp[i][j][l] == oo) continue;
        int d1 = nxt[j][a[i + 1][0]];
        int d2 = nxt[j][1 - a[i + 1][0]];
        bool t1 = (d1 == m), t2 = (d2 == m);
        if (t1) d1 = nw;
        if (t2) d2 = nw;
        upd(_dp[i + 1][d1][l + t1], _dp[i][j][l]);
        upd(_dp[i + 1][d2][l + t2], _dp[i][j][l] + 1);
      }
    }
  }
  for (int l = 0; l < k; l++) {
    int ans = oo;
    for (int i = 0; i <= m; i++) {
      upd(ans, _dp[n][i][l]);
    }
    if (ans == oo) ans = -1;
    printf("%d ", ans);
  }
  return 0;
}
