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.OutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Hamed Valizadeh (havaliza@gmail.com)
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastInputReader in = new FastInputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    private static final int INF = 1000 * 1000 * 1000;

    String string;
    String pattern;

    int[][] minCost;
    int[] minEnd;

    public void solve(int testNumber, FastInputReader in, PrintWriter out) {
        string = in.next();
        pattern = in.next();

        minCost = new int[string.length() + 1][string.length() + 1];
        minEnd = new int[string.length()];

        for (int i = 0; i < string.length(); i++) {
            int matched = 0;
            minEnd[i] = -1;
            for (int j = i; j < string.length(); j++) {
                if (pattern.charAt(matched) == string.charAt(j)) {
                    matched++;
                    if (matched == pattern.length()) {
                        minEnd[i] = j + 1;
                        break;
                    }
                }
            }
        }

        for (int count = 1; count <= string.length(); count++) {
            minCost[string.length()][count] = INF;
            for (int i = string.length() - 1; i >= 0; i--) {
                minCost[i][count] = minCost[i + 1][count];

                if (minEnd[i] == -1)
                    continue;

                int skipped = minEnd[i] - i - pattern.length();
                minCost[i][count] = Math.min(minCost[i][count], minCost[minEnd[i]][count - 1] + skipped);
            }
        }

        int[] ans = new int[string.length() + 1];

        for (int count = 1; count <= string.length(); count++) {
            int min = minCost[0][count];
            int max = string.length() - count * pattern.length();
            for (int i = min; i <= max; i++)
                ans[i] = count;
        }

        for (int x: ans)
            out.print("" + x + " ");
        out.println();
    }
}

class FastInputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public FastInputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}

