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

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

    static class TaskC {
        static int[] from;
        static String s;
        static String P;
        static int n;
        static int p;
        static int INF = 1000000;

        void fill() {
            TreeSet<Integer>[] chars = new TreeSet[26];
            for (int i = 0; i < 26; i++) {
                chars[i] = new TreeSet();
            }

            for (int i = 0; i < n; i++) {
                chars[s.charAt(i) - 'a'].add(i);
            }
            Arrays.fill(from, -1);
            FOR:
            for (int i = (n - 1); i >= 0; i--) {
                if (s.charAt(i) != P.charAt(0)) {
                    continue;
                }
                int cur = i;
                for (int j = 1; j < p; j++) {
                    if (chars[P.charAt(j) - 'a'].higher(cur) == null) {
                        continue FOR;
                    } else {
                        cur = chars[P.charAt(j) - 'a'].higher(cur);
                    }
                }
                from[i] = cur;
            }
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            s = in.next();
            P = in.next();
            n = s.length();
            p = P.length();

            from = new int[n];
            fill();

            int[][] dp = new int[n / p + 1][n];
            for (int i = 1; i < dp.length; i++) {
                Arrays.fill(dp[i], INF);
            }

            for (int m = 1; m <= (n / p); m++) {
                for (int j = (n - 1); j >= 0; j--) {
                    if (s.charAt(j) != P.charAt(0)) {
                        if (j + 1 < n) {
                            dp[m][j] = dp[m][j + 1];
                        }
                    } else {
                        int one = from[j];
                        if (one == -1) {
                            if (j + 1 < n) {
                                dp[m][j] = dp[m][j + 1];
                            }
                        } else {
                            if (j + 1 < n) {
                                dp[m][j] = Math.min(dp[m][j], dp[m][j + 1]);
                            }
                            // number of removal of chars;
                            int pos = one - j + 1 - p;
                            if (one == n - 1 && m != 1) {
                                continue;
                            }
                            if (m == 1) {
                                dp[m][j] = Math.min(pos, dp[m][j]);
                            } else {
                                pos += dp[m - 1][one + 1];
                                dp[m][j] = Math.min(pos, dp[m][j]);
                            }
                        }
                    }
                }
            }

        /*for(int i=1; i<=(n/p); i++){
            // Min number of removal to get i pattern
            dp[i][0]
        }*/
            int max = 0;
            for (int i = 0; i < dp.length; i++) {
                if (dp[i][0] < INF) {
                    max = Math.max(i, max);
                }
            }
       /* for(int i=0; i<dp.length; i++){
            System.out.println("dp[" + i + " ][0]=" + dp[i][0]);
        }
        for(int i=0; i<from.length; i++){
            System.out.println(from[i]);
        }
*/
        /*int j=1;
        int[] mins= new int[max+1];
        for(int i=0; i<mins.length; i++){
            mins[i]= dp[i][0];
        }*/
            for (int i = 0; i <= n; i++) {
                if (i > (n - max * p)) {
                    int j = i;
                    j -= (n - max * p);
                    int k = (int) Math.ceil((double) j / p);
                    out.print((max - k) + " ");
                } else {
                    int j = 0;
                    while (dp[j][0] <= i) {
                        j++;
                        if (j == (max + 1)) {
                            break;
                        }
                    }
                    if (j == (max + 1)) {
                        out.print(max + " ");
                    } else {
                        out.print((j - 1) + " ");
                    }
                }
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(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();
        }

    }
}

