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>
const int MAX_N = 2005;
std::string s, p;
int n, m, f[MAX_N][26], t[MAX_N], g[MAX_N][26], h[MAX_N][MAX_N], x[MAX_N];
void mini(int &a, const int b) {
  if (a > b) a = b;
}
void maxi(int &a, const int b) {
  if (a < b) a = b;
}
int main() {
  std::cin >> s >> p;
  n = s.size();
  m = p.size();
  std::fill(f[n], f[n] + 26, MAX_N);
  for (int i = n - 1; i >= 0; --i)
    for (int j = 0; j < 26; ++j)
      f[i][j] = s[i] - 'a' == j ? i + 1 : f[i + 1][j];
  for (int i = 1, q = 0; i < m; ++i) {
    while (q && p[q] != p[i]) q = t[q - 1];
    t[i] = q += p[q] == p[i];
  }
  g[0][p[0] - 'a'] = 1;
  for (int i = 1; i < m; ++i)
    for (int j = 0; j < 26; ++j) {
      int q = i;
      while (q && p[q] - 'a' != j) q = t[q - 1];
      g[i][j] = q + (p[q] - 'a' == j);
    }
  for (int i = 0; i < MAX_N; ++i) std::fill(h[i] + !i, h[i] + MAX_N, MAX_N);
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= n; ++j) {
      const int p = h[i][j];
      if (p <= n) {
        const int c = j / m, r = j % m;
        maxi(x[n - i], c);
        if (p < n)
          for (int k = 0; k < 26; ++k) mini(h[i + 1][c * m + g[r][k]], f[p][k]);
      }
    }
  for (int i = 0; i <= n; ++i) std::cout << x[i] << ' ';
  std::cout << '\n';
}
