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;
int ar[505];
char ch[505], ch1[505], tem[505 + 505];
int n, m, ii, k;
short int dp[505][505][505], dp1[505][2];
bool vis[505][505][505], vis1[505][2];
int Prefix_func(int id, int add) {
  if (vis1[id][add]) return dp1[id][add];
  vis1[id][add] = 1;
  int sz = m + id + 1;
  int l = 1;
  if (id + 1 != m) sz++, l = 0;
  tem[sz] = '\0';
  for (int i = 0; i < m; i++) tem[i] = ch1[i];
  tem[m] = '#';
  for (int i = m + 1; l < id; l++, i++) tem[i] = ch1[l];
  tem[sz - 1] = add + '0';
  vector<int> pi(sz);
  for (int i = 1; i < sz; i++) {
    int j = pi[i - 1];
    while (j > 0 && tem[i] != tem[j]) j = pi[j - 1];
    if (tem[j] == tem[i]) j++;
    pi[i] = j;
  }
  return dp1[id][add] = pi[sz - 1];
}
int func(int id1, int id2, int have) {
  if (id1 == n) {
    if (have == 0) return 0;
    return 505;
  }
  if (have < 0) return 505;
  if (vis[id1][id2][have]) return dp[id1][id2][have];
  vis[id1][id2][have] = 1;
  int re = 505;
  if (ch[id1] == '0') {
    int got = 0;
    if (id2 == m - 1 && ch1[id2] == ch[id1]) got++;
    int nxt = Prefix_func(id2, 0);
    re = min(re, func(id1 + 1, nxt, have - got));
  } else {
    int got = 0;
    if (id2 == m - 1 && ch1[id2] == '0') got++;
    int nxt = Prefix_func(id2, 0);
    re = min(re, 1 + func(id1 + 1, nxt, have - got));
  }
  if (ch[id1] == '1') {
    int got = 0;
    if (id2 == m - 1 && ch1[id2] == ch[id1]) got++;
    int nxt = Prefix_func(id2, 1);
    re = min(re, func(id1 + 1, nxt, have - got));
  } else {
    int got = 0;
    if (id2 == m - 1 && ch1[id2] == '1') got++;
    int nxt = Prefix_func(id2, 1);
    re = min(re, 1 + func(id1 + 1, nxt, have - got));
  }
  return dp[id1][id2][have] = re;
}
void solve() {
  scanf("%d%d%s%s", &n, &m, ch, ch1);
  for (int i = 0; i <= n - m + 1; i++) {
    int re = func(0, 0, i);
    if (re > n) {
      printf("-1");
    } else
      printf("%d", re);
    if (i == n - m + 1)
      printf("\n");
    else
      printf(" ");
  }
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}
