Dreamoon has a string s and a pattern string p. He first removes exactly x characters from s obtaining string s' as a result. Then he calculates <image> that is defined as the maximal number of non-overlapping substrings equal to p that can be found in s'. He wants to make this number as big as possible.

More formally, let's define <image> as maximum value of <image> over all s' that can be obtained by removing exactly x characters from s. Dreamoon wants to know <image> for all x from 0 to |s| where |s| denotes the length of string s.

Input

The first line of the input contains the string s (1 ≤ |s| ≤ 2 000).

The second line of the input contains the string p (1 ≤ |p| ≤ 500).

Both strings will only consist of lower case English letters.

Output

Print |s| + 1 space-separated integers in a single line representing the <image> for all x from 0 to |s|.

Examples

Input

aaaaa
aa


Output

2 2 1 1 0 0


Input

axbaxxb
ab


Output

0 1 1 2 1 1 0 0

Note

For the first sample, the corresponding optimal values of s' after removal 0 through |s| = 5 characters from s are {"aaaaa", "aaaa", "aaa", "aa", "a", ""}. 

For the second sample, possible corresponding optimal values of s' are {"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""}.
#include <bits/stdc++.h>
using namespace std;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcountll(s);
}
const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
  if (rsz <= 0) {
    ptr = 0;
    rsz = (int)fread(bf, 1, bfsz, stdin);
    if (rsz <= 0) return EOF;
  }
  --rsz;
  return bf[ptr++];
}
void ga(char &c) {
  c = EOF;
  while (!isalpha(c)) c = gc();
}
int gs(char s[]) {
  int l = 0;
  char c = gc();
  while (isspace(c)) c = gc();
  while (c != EOF && !isspace(c)) {
    s[l++] = c;
    c = gc();
  }
  s[l] = '\0';
  return l;
}
template <class T>
bool gi(T &v) {
  v = 0;
  char c = gc();
  while (c != EOF && c != '-' && !isdigit(c)) c = gc();
  if (c == EOF) return false;
  bool neg = c == '-';
  if (neg) c = gc();
  while (isdigit(c)) {
    v = v * 10 + c - '0';
    c = gc();
  }
  if (neg) v = -v;
  return true;
}
template <class T>
T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
string s, t;
int n, m;
int f[2005][2005], vt[2005], res[2005];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  memset(f, 0x3f, sizeof(f));
  f[0][0] = 0;
  cin >> s >> t;
  n = ((int)(s).size());
  m = ((int)(t).size());
  for (int i = 0; i <= n; i++) vt[i] = i % m;
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j <= i; j++)
      if (f[i][j] < 1000000005) {
        int d = vt[j];
        if (d == 0)
          f[i + 1][j] = min(f[i + 1][j], f[i][j]);
        else
          f[i + 1][j] = min(f[i + 1][j], f[i][j] + 1);
        if (s[i] == t[d]) {
          f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
        }
      }
  memset(res, 0, sizeof(res));
  for (int i = (0); i <= (n + 1); ++i) {
    res[i] = (n - i) / m;
  }
  for (int i = 0;; i++) {
    int l = f[n][i * m], r = f[n][(i + 1) * m] - 1;
    if (r >= 1000000005) r = n;
    for (int j = l; j <= r; j++) res[j] = min(res[j], i);
    if (r >= n) break;
  }
  for (int i = (0); i <= (n); ++i) cout << res[i] << " ";
  return 0;
}
