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 std::cin;
using std::complex;
using std::cout;
using std::endl;
using std::fixed;
using std::greater;
using std::ios_base;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multiset;
using std::next_permutation;
using std::ostream;
using std::pair;
using std::prev_permutation;
using std::random_shuffle;
using std::reverse;
using std::set;
using std::setprecision;
using std::sort;
using std::string;
using std::swap;
using std::upper_bound;
using std::vector;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
const long long N = 2e3 + 5;
long long dp[N][N];
long long res[N];
int main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  string s, p;
  getline(cin, s);
  getline(cin, p);
  long long n = s.length();
  long long k = p.length();
  s = ' ' + s;
  p = ' ' + p;
  for (long long i = (1); i <= (N - 2); ++i) {
    dp[0][i] = N;
  }
  for (long long i = (1); i <= (n); ++i) {
    long long need = k;
    for (long long l = (1); l <= (N - 2); ++l) {
      dp[i][l] = dp[i - 1][l];
    }
    for (long long j = i; j >= 0; j--) {
      if (need == 0) {
        long long to_rem = i - j - k;
        for (long long l = (1); l <= (N - 2); ++l) {
          dp[i][l] = min(dp[i - 1][l], dp[j][l - 1] + to_rem);
        }
        break;
      }
      if (s[j] == p[need]) {
        need--;
      }
    }
  }
  for (long long i = (1); i <= (n); ++i) {
    for (long long j = (dp[n][i]); j <= (min(dp[n][i + 1] - 1, N - 1)); ++j) {
      res[j] = i;
    }
  }
  for (long long i = (0); i <= (n); ++i) {
    cout << min(res[i], (n - i) / k) << " ";
  }
  cout << endl;
  return 0;
}
