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;
char s[2005], p[505];
int sl, pl;
const int N = 4005;
int dp[N][N];
int fl[N];
const int INF = 100 * 1000 * 1000;
bool read() {
  if (scanf("%s%s", s, p) <= 0) return false;
  sl = strlen(s);
  pl = strlen(p);
  return true;
}
int ftr[N][N];
inline void update(int* f, int pos, int r) {
  for (; pos < N; pos |= pos + 1) f[pos] = max(f[pos], r);
}
inline int get(int* f, int r) {
  int res = -INF;
  for (; r >= 0; r = (r & (r + 1)) - 1) res = max(res, f[r]);
  return res;
}
void solve() {
  for (int len = 1; len <= sl; ++len)
    for (int i = 0; i < int(sl); ++i) {
      int j = i + len - 1;
      if (j >= sl) continue;
      if (i == j)
        dp[i][j] = (s[i] == p[0]);
      else {
        int pr = dp[i][j - 1];
        dp[i][j] = dp[i][j - 1] + (pr != pl && s[j] == p[pr]);
      }
    }
  for (int i = 0; i < int(sl); ++i) {
    fl[i] = -1;
    for (int j = i; j >= 0; --j)
      if (dp[j][i] == pl) {
        fl[i] = i - j + 1;
        break;
      }
  }
  for (int i = 0; i < int(N); ++i)
    for (int j = 0; j < int(N); ++j) dp[i][j] = ftr[i][j] = -INF;
  dp[0][0] = 0;
  update(ftr[0], 0, 0);
  for (int i = 1; i <= sl; ++i)
    for (int cut = 0; cut <= i; ++cut) {
      dp[i][cut] = dp[i - 1][cut];
      if (cut >= 0) dp[i][cut] = max(dp[i][cut], dp[i - 1][cut - 1]);
      int l = fl[i - 1];
      if (l != -1) {
        if (i - cut - pl >= 0)
          dp[i][cut] = max(dp[i][cut], get(ftr[i - cut - pl], i - l) + 1);
      }
      update(ftr[i - cut], i, dp[i][cut]);
    }
  for (int c = 0; c <= sl; ++c) printf("%d ", dp[sl][c]);
}
int main() {
  while (read()) solve();
  return 0;
}
