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;
vector<vector<long long> > matmul(vector<vector<long long> > &a,
                                  vector<vector<long long> > &b) {
  int i, j, k, n = a.size();
  vector<vector<long long> > ans(n, vector<long long>(n));
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      long long temp = 0;
      for (k = 0; k < n; k++)
        temp = (temp + a[i][k] * b[k][j]) % (1000000007LL);
      ans[i][j] = temp;
    }
  return ans;
}
vector<vector<long long> > matpwr(vector<vector<long long> > &a, long long p) {
  int n = a.size();
  vector<vector<long long> > ans(n, vector<long long>(n));
  for (int i = 0; i < n; i++) ans[i][i] = 1;
  while (p) {
    if (p & 1) ans = matmul(ans, a);
    a = matmul(a, a);
    p >>= 1;
  }
  return ans;
}
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long invMod(long long n, long long mod = (1000000007LL)) {
  return pwr(n, mod - 2, mod);
}
string str1, str2;
int n1, n2, rightmostStartPos[2002], DP[2002][2002];
int dp(int i, int toRemove) {
  if (i == 0) {
    if (toRemove == 0) return 0;
    return -(100000005);
  }
  if (DP[i][toRemove] != -1) return DP[i][toRemove];
  int ans = -(100000005);
  if (toRemove > 0) ans = max(ans, dp(i - 1, toRemove - 1));
  ans = max(ans, dp(i - 1, toRemove));
  if (rightmostStartPos[i] != -1) {
    int deleted = (i - rightmostStartPos[i] + 1) - n2;
    if (deleted <= toRemove)
      ans = max(ans, 1 + dp(rightmostStartPos[i] - 1, toRemove - deleted));
  }
  return DP[i][toRemove] = ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> str1 >> str2;
  n1 = str1.length();
  n2 = str2.length();
  memset(rightmostStartPos, -1, sizeof(rightmostStartPos));
  for (int i = 1; i <= n1; i++) {
    int cnt = 0, pos = i;
    while (cnt < n2 && pos > 0) {
      if (str1[pos - 1] == str2[n2 - 1 - cnt]) cnt++;
      pos--;
    }
    if (cnt == n2) rightmostStartPos[i] = pos + 1;
  }
  memset(DP, -1, sizeof(DP));
  for (int x = 0; x <= n1; x++) cout << dp(n1, x) << " ";
  return 0;
}
