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;
template <class T1>
void debug(T1 e) {
  cout << e << endl;
}
template <class T1, class T2>
void debug(T1 e1, T2 e2) {
  cout << e1 << "\t" << e2 << endl;
}
template <class T1, class T2, class T3>
void debug(T1 e1, T2 e2, T3 e3) {
  cout << e1 << "\t" << e2 << "\t" << e3 << endl;
}
template <class T1, class T2, class T3, class T4>
void debug(T1 e1, T2 e2, T3 e3, T4 e4) {
  cout << e1 << "\t" << e2 << "\t" << e3 << "\t" << e4 << endl;
}
template <class T1, class T2, class T3, class T4, class T5>
void debug(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5) {
  cout << e1 << "\t" << e2 << "\t" << e3 << "\t" << e4 << "\t" << e5 << endl;
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void debug(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6) {
  cout << e1 << "\t" << e2 << "\t" << e3 << "\t" << e4 << "\t" << e5 << "\t"
       << e6 << endl;
}
template <class T>
void debug(vector<vector<T> > e, int row, int col) {
  int i, j;
  for (i = 0; i < row; i++) {
    for (j = 0; j < col; j++) cout << e[i][j] << " ";
    cout << endl;
  }
  cout << endl;
}
template <class T>
void debug(vector<basic_string<T> > e, int row, int col) {
  int i, j;
  for (i = 0; i < row; i++) {
    for (j = 0; j < col; j++) cout << e[i][j];
    cout << endl;
  }
  cout << endl;
}
template <class T>
void debug(T e[110][110], int row, int col) {
  int i, j;
  for (i = 0; i < row; i++) {
    for (j = 0; j < col; j++) cout << e[i][j] << " ";
    cout << endl;
  }
}
template <class T>
string toString(T n) {
  ostringstream oss;
  oss << n;
  oss.flush();
  return oss.str();
}
int toInt(string s) {
  int r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
bool isVowel(char ch) {
  ch = tolower(ch);
  if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
    return true;
  return false;
}
bool isUpper(char c) { return c >= 'A' && c <= 'Z'; }
bool isLower(char c) { return c >= 'a' && c <= 'z'; }
int ans[3000];
string s, p;
int dp[2100][2100];
int dprec(int ina, int inb) {
  if (inb < 0) return 0;
  if (ina < 0) return 1000000000;
  int &ret = dp[ina][inb];
  if (ret != -1) return ret;
  int in = inb % ((int)p.size());
  int add = 1;
  if (in == ((int)p.size()) - 1) add = 0;
  ret = dprec(ina - 1, inb) + add;
  if (s[ina] == p[in]) ret = min(ret, dprec(ina - 1, inb - 1));
  return ret;
}
int main() {
  while (cin >> s >> p) {
    int i;
    memset(dp, -1, sizeof(dp));
    memset(ans, 0, sizeof(ans));
    for (i = 0; i <= ((int)s.size()); i += ((int)p.size())) {
      int mi = dprec(((int)s.size()) - 1, i - 1);
      if (mi >= 1000000000) break;
      int ma = ((int)s.size()) - i;
      for (int j = mi; j <= ma; j++) ans[j] = (i / ((int)p.size()));
    }
    printf("%d", ans[0]);
    for (i = 1; i <= ((int)s.size()); i++) printf(" %d", ans[i]);
    cout << endl;
  }
  return 0;
}
