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 PI = acos(-1), EPS = 1e-8;
const int mod = 1000000007;
const int dr[]{-1, -1, 0, 1, 1, 1, 0, -1};
const int dc[]{0, 1, 1, 1, 0, -1, -1, -1};
void run() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
string s, p;
vector<pair<int, int>> match;
int mem[2009][2009];
int solve(int idx, int rem) {
  if (rem < 0) return -0x3f3f3f3fLL;
  if (idx == (int)(s.size())) return -0x3f3f3f3fLL * (rem != 0);
  int& rt = mem[idx][rem];
  if (~rt) return rt;
  rt = solve(idx + 1, rem - 1);
  rt = max(rt, solve(idx + 1, rem));
  if (~match[idx].second)
    rt = max(rt, 1 + solve(match[idx].first, rem - match[idx].second));
  return rt;
}
int main() {
  run();
  memset(mem, -1, sizeof(mem));
  cin >> s >> p;
  match = vector<pair<int, int>>((int)(s.size()));
  for (int i = 0; i < (int)(s.size()); i++) {
    int j = 0, k = i;
    while (j < (int)(p.size()) && k < (int)(s.size())) {
      if (p[j] == s[k]) j++;
      k++;
    }
    match[i].first = k;
    if (j == (int)(p.size()))
      match[i].second = k - i - (int)(p.size());
    else
      match[i].second = -1;
  }
  for (int i = 0; i <= (int)(s.size()); i++) cout << solve(0, i) << " ";
}
