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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
void __print(long long x) { cerr << x; }
void __print(int32_t x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long long MOD = 1e9 + 7;
const long long MOD1 = 998244353;
const long long N = 2e5 + 5;
const long long INF = 2e9;
const long double EPS = 1e-12;
const long double PI = 3.141592653589793116;
int32_t dp[505][505][505];
long long pre[505][2];
int32_t main() {
  std::ios_base::sync_with_stdio(0);
  cout.tie(nullptr);
  long long n, m;
  cin >> n >> m;
  string a, b;
  cin >> a >> b;
  for (long long i = 0; i < m; i++) {
    string str = b.substr(0, i + 1);
    str.push_back('0');
    for (long long j = 0; j < (long long)str.size(); j++) {
      string tmp = str.substr(j);
      if ((long long)tmp.size() > (long long)b.size()) continue;
      if (tmp == b.substr(0, (long long)tmp.size())) {
        pre[i + 1][0] = (long long)tmp.size();
        break;
      }
    }
    str.pop_back();
    str.push_back('1');
    for (long long j = 0; j < (long long)str.size(); j++) {
      string tmp = str.substr(j);
      if ((long long)tmp.size() > (long long)b.size()) continue;
      if (tmp == b.substr(0, (long long)tmp.size())) {
        pre[i + 1][1] = (long long)tmp.size();
        break;
      }
    }
  }
  pre[0][0] = (b[0] == '0');
  pre[0][1] = (b[0] == '1');
  for (long long i = 0; i < 505; i++) {
    for (long long j = 0; j < 505; j++) {
      for (long long k = 0; k < 505; k++) {
        dp[i][j][k] = INF;
      }
    }
  }
  for (long long i = 0; i < n; i++) {
    if (i == 0) {
      if (a[0] == '0') {
        dp[0][pre[i][1]][(pre[i][1] == m)] = 1;
        dp[0][pre[i][0]][(pre[i][0] == m)] = 0;
      } else {
        dp[0][pre[i][0]][(pre[i][0] == m)] = 1;
        dp[0][pre[i][1]][(pre[i][1] == m)] = 0;
      }
      continue;
    }
    for (long long j = 0; j <= m; j++) {
      for (long long k = 0; k <= n + m + 3; k++) {
        if (dp[i - 1][j][k] == INF) continue;
        int32_t &res0 = dp[i][pre[j][0]][k + (pre[j][0] == m)];
        int32_t &res1 = dp[i][pre[j][1]][k + (pre[j][1] == m)];
        res0 = min((int32_t)res0, dp[i - 1][j][k] + int32_t(a[i] != '0'));
        res1 = min((int32_t)res1, dp[i - 1][j][k] + int32_t(a[i] != '1'));
      }
    }
  }
  for (long long k = 0; k <= n - m + 1; k++) {
    int32_t ans = INF;
    for (long long j = 0; j <= m; j++) {
      ans = min(ans, dp[n - 1][j][k]);
    }
    if (ans == INF) ans = -1;
    cout << ans << ' ';
  }
  return 0;
}
