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", ""}.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Round272_C {

    char[] T;
    char[] P;

    int[][] memo;
    int[] needed;
    boolean[] valid;

    public int go(int index, int toRemove) {

    if (toRemove < 0)
        return -1 << 25;
    if (index == T.length)
        return (toRemove == 0) ? 0 : -1 << 25;
    if (memo[index][toRemove] != -1)
        return memo[index][toRemove];

    int ret = -1 << 25;
    ret = Math.max(ret, go(index + 1, toRemove - 1));
    if (!(valid[index] && needed[index] == 0)) {
        ret = Math.max(ret, go(index + 1, toRemove));
    }

    if (valid[index]) {
        ret = Math.max(
            ret,
            1 + go(index + P.length + needed[index], toRemove
                - needed[index]));
    }
    return memo[index][toRemove] = ret;
    }

    public void solve() throws Exception {
    InputReader in = new InputReader();
    T = in.next().toCharArray();
    P = in.next().toCharArray();
    int N = T.length;
    int M = P.length;

    needed = new int[T.length];
    valid = new boolean[T.length];
    Arrays.fill(needed, 1 << 25);
    for (int i = 0; i < N; i++) {
        int j = 0;
        int matches = 0;
        int bad = 0;
        int index = i;
        while (index < N && j < M && matches < M) {
        if (T[index] == P[j]) {
            ++matches;
            ++index;
            ++j;
        } else {
            ++index;
            ++bad;
        }
        }
        if (matches == M) {
        valid[i] = true;
        }
        needed[i] = bad;
    }
    memo = new int[N + 2][N + 2];
    for (int i = 0; i < memo.length; i++)
        Arrays.fill(memo[i], -1);
    StringBuffer ret = new StringBuffer();
    ret.append(go(0, 0) + "");
    for (int i = 1; i <= N; i++) {
        ret.append(' ').append("" + go(0, i));
    }
    System.out.println(ret);
    }

    public static void main(String[] args) throws Exception {
    new Round272_C().solve();
    }

    static class InputReader {
    BufferedReader in;
    StringTokenizer st;

    public InputReader() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(in.readLine());

    }

    public String next() throws IOException {

        while (!st.hasMoreElements())
        st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }

    public int nextInt() throws NumberFormatException, IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws NumberFormatException, IOException {
        return Long.parseLong(next());
    }
    }
}
