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>
#pragma comment(linker, "/STACK:20000000")
using namespace std;
int ri() {
  int x;
  scanf("%d", &x);
  return x;
}
long long rll() {
  long long x;
  scanf("%lld", &x);
  return x;
}
string s;
string p;
int need[2050];
int dp[2050][2050];
int go(int pos, int ost) {
  if (pos == s.length()) return (ost == 0 ? 0 : -100500);
  if (dp[pos][ost] != -1) return dp[pos][ost];
  int res = go(pos + 1, ost);
  if (ost) res = max(res, go(pos + 1, ost - 1));
  int w = (need[pos] - pos + 1) - p.length();
  if (w <= ost) res = max(res, go(need[pos] + 1, ost - w) + 1);
  return dp[pos][ost] = res;
}
void solve() {
  cin >> s >> p;
  for (int i = 0; i < s.length(); i++) {
    if (i + p.length() <= s.length()) {
      int pos = 0;
      for (int k = i; k < s.length(); k++) {
        if (s[k] == p[pos]) pos++;
        if (pos == p.length()) {
          need[i] = k;
          break;
        }
      }
      if (pos != p.length()) need[i] = 100500;
    } else
      need[i] = 100500;
  }
  memset(dp, -1, sizeof(dp));
  for (int i = 0; i < s.length(); i++) {
    int v = go(0, i);
    cout << v << " ";
  }
  cout << 0 << endl;
}
int main() {
  solve();
  return 0;
}
