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>
namespace {
using namespace std;
using ll = long long;
using ii = std::pair<int, int>;
using vi = std::vector<int>;
using vii = std::vector<ii>;
using vll = std::vector<ll>;
using ss = std::pair<std::string, std::string>;
using vss = std::vector<ss>;
const int INF = 1e9;
const int MAX_COUNT = 1e5;
const int MOD = 1e9 + 7;
template <typename T>
inline T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T, typename U>
inline std::pair<T, U> mpair(T a, U b) {
  return std::make_pair(a, b);
}
char sStr[2100], tStr[600];
int sSize = 0, tSize = 0;
int A[2100];
int DP[2100][2100];
int solveTopDown(int idx, int removalLeft) {
  if (idx > sSize || (removalLeft > 0 && idx == sSize) || removalLeft < 0)
    return -1;
  if (idx == sSize) return 0;
  if (DP[idx][removalLeft] != -2) return DP[idx][removalLeft];
  int removeRes = solveTopDown(idx + 1, removalLeft - 1);
  int skipRes = solveTopDown(idx + 1, removalLeft);
  int res = std::max(removeRes, skipRes);
  if (A[idx] > 0) {
    int delNumber = A[idx] - tSize;
    int startSeqRes = solveTopDown(idx + A[idx], removalLeft - delNumber);
    if (startSeqRes != -1) res = std::max(res, startSeqRes + 1);
  }
  DP[idx][removalLeft] = res;
  return res;
}
}  // namespace
int main(int argc, const char* argv[]) {
  std::ios_base::sync_with_stdio(false);
  std::cin >> sStr >> tStr;
  sSize = (int)strlen(sStr);
  tSize = (int)strlen(tStr);
  for (int i = 0; i < sSize; ++i) {
    bool possible = true;
    int srcI = i;
    for (int j = 0; j < tSize;) {
      if (sStr[srcI] == tStr[j]) {
        ++j;
      }
      ++srcI;
      if (srcI >= sSize && j != tSize) {
        possible = false;
        break;
      }
    }
    A[i] = possible ? srcI - i : -1;
  }
  std::fill_n(&DP[0][0], 2100 * 2100, -2);
  for (int k = 0; k <= sSize; ++k) {
    int res = solveTopDown(0, k);
    std::cout << res << " ";
  }
  std::cout << std::endl;
  return 0;
}
