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.*;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * Codeforces 476E - Dreamoon and Strings
 * Created by Darren on 14-10-18.
 */
public class E {
    Reader in = new Reader(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        new E().run();
    }

    char[] s, p;
    int n, m;
    int[][] dp;

    void run() throws IOException {
        s = in.readLine().toCharArray();
        p = in.readLine().toCharArray();
        n = s.length;
        m = p.length;

        int a[] = new int[n+1];
        for (int i = m; i <= n; i++) {
            int ind = m-1, j = i-1;
            for (; j >= 0 && ind >= 0; j--) {
                if (s[j] == p[ind]) {
                    ind--;
                }
            }
            if (ind < 0)
                a[i] = i - j - 1;
        }

        dp = new int[n+1][n+1];
        for (int i = 0; i <= n; i++)
            Arrays.fill(dp[i], -1);
        // Base case: i = 0, j = 0
        dp[0][0] = 0;
        // Base case: j = 0
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i-1][0];
            if (a[i] == m) {
                dp[i][0] = Math.max(dp[i][0], dp[i-a[i]][0] + 1);
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]);
                if (a[i] > 0 && j - (a[i] - m) >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-a[i]][j-(a[i]-m)]+1);
                }
            }
        }

        for (int j = 0; j <= n; j++) {
            out.print(dp[n][j]);
            out.print(' ');
        }
        out.flush();
    }

    static class Reader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public Reader(InputStream input) {
            reader = new BufferedReader(new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /** get next word */
        String nextToken() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer( reader.readLine() );
            }
            return tokenizer.nextToken();
        }

        String readLine() throws IOException {
            return reader.readLine();
        }

        int nextInt() throws IOException {
            return Integer.parseInt( nextToken() );
        }

        long nextLong() throws IOException {
            return Long.parseLong( nextToken() );
        }

        double nextDouble() throws IOException {
            return Double.parseDouble( nextToken() );
        }
    }
}
