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;
int inf = 1e9;
int l1, l2, f[2010][2010], g[2010], G[2010], Min[2010];
char S[2010], T[510];
struct BIT {
  int c[2010];
  inline int lowbit(int x) { return x & (-x); }
  void init() {
    for (int i = 1; i <= l1 + 1; i++) c[i] = inf;
  }
  int Get(int i) {
    i++;
    int ans = inf;
    for (; i > 0; i -= lowbit(i)) ans = min(c[i], ans);
    return ans;
  }
  void Add(int i, int x) {
    i++;
    for (; i <= l1 + 1; i += lowbit(i)) c[i] = min(c[i], x);
  }
} Tt[2010];
inline void read(int& x) {
  char ch = getchar();
  int mk = 1;
  for (; (ch < '0' || ch > '9') && ch != '-'; ch = getchar())
    ;
  if (ch == '-') mk = -1, ch = getchar();
  for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
  x *= mk;
}
int main() {
  scanf("%s%s", S + 1, T + 1);
  l1 = strlen(S + 1);
  l2 = strlen(T + 1);
  for (int i = 1; i <= l1; i++)
    if (S[i] == T[1]) {
      int t = 2, j = i + 1;
      for (; j <= l1 && t <= l2; j++) {
        if (S[j] == T[t]) t++;
      }
      if (t > l2) {
        j--;
        g[i] = j - i + 1;
        G[j] = j - i + 1;
      }
    }
  for (int i = 0; i <= l1; i++) Tt[i].init();
  for (int i = 0; i <= l1; i++)
    for (int j = 0; j <= l1; j++) f[i][j] = inf;
  f[0][0] = 0;
  Tt[0].Add(0, 0);
  for (int i = 1; i <= l1; i++)
    if (G[i]) {
      for (int j = 1; j <= l1; j++) {
        int pre = i - G[i];
        int Min = Tt[j - 1].Get(pre);
        if (Min != inf) {
          f[i][j] = Min + G[i];
          Tt[j].Add(i, f[i][j]);
        }
      }
    }
  for (int i = 1; i <= l1; i++) Min[i] = inf;
  for (int i = 1; i <= l1; i++)
    for (int j = 1; j <= l1; j++) Min[j] = min(Min[j], f[i][j]);
  int now = 0, Max = 0;
  for (int i = 1; i <= l1; i++)
    if (Min[i] != inf) {
      Max = i;
      Min[i] -= i * l2;
    }
  for (int i = 0; i <= l1; i++)
    if (Max * l2 >= l1 - i) {
      printf("%d ", (l1 - i) / l2);
    } else {
      for (; now + 1 <= Max && Min[now + 1] <= i; now++)
        ;
      printf("%d ", now);
    }
  printf("\n");
  return 0;
}
