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;
const long double EPS = 1e-9;
const int MAXN = 2e3 + 10;
const int INF = 1e9;
char s[MAXN];
int ns;
char p[MAXN];
int np;
int min_x[MAXN][MAXN];
int r[MAXN];
int min_l[MAXN];
int ans[MAXN];
int main() {
  gets(s);
  ns = strlen(s);
  gets(p);
  np = strlen(p);
  for (int l = 0; l < (int)ns; ++l) {
    r[l] = INF;
    int i = 0;
    for (int j = l; j < ns && i < np; ++j) {
      if (s[j] == p[i]) {
        ++i;
      }
      if (i == np) {
        r[l] = j;
        break;
      }
    }
  }
  r[ns] = INF;
  min_l[ns] = ns;
  for (int l = ((int)ns) - 1; l >= 0; --l) {
    min_l[l] = l;
    if (r[min_l[l + 1]] < r[min_l[l]]) {
      min_l[l] = min_l[l + 1];
    }
  }
  for (int i = 0; i < (int)ns + 1; ++i)
    for (int cnt = 0; cnt < (int)ns + 1; ++cnt) min_x[i][cnt] = INF;
  min_x[0][0] = 0;
  for (int i = 0; i < (int)ns + 1; ++i) {
    for (int cnt = 0; cnt < (int)ns + 1; ++cnt) {
      int& cur = min_x[i][cnt];
      if (cur >= INF) {
        continue;
      }
      int& nxt1 = min_x[i + 1][cnt];
      nxt1 = min(nxt1, cur);
      ans[cur] = max(ans[cur], cnt);
      int next_l = min_l[i];
      if (r[next_l] >= INF) {
        continue;
      }
      int& nxt = min_x[r[next_l] + 1][cnt + 1];
      nxt = min(nxt, cur + (r[next_l] - next_l + 1) - np);
    }
  }
  for (int x = 0; x < (int)ns; ++x) {
    ans[x + 1] = max(ans[x + 1], ans[x]);
    while (ns - (x + 1) - ans[x + 1] * np < 0) --ans[x + 1];
  }
  for (int x = 0; x < (int)ns + 1; ++x) {
    printf("%d ", ans[x]);
  }
  return 0;
}
