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.text.DecimalFormat;
import java.util.*;

public class Main {

    public static final DecimalFormat DF_3 = new DecimalFormat("0.000");
    private static final long MOD = 1000000007;


    static int[] readArray(int size, InputReader in, boolean subOne) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt() + (subOne ? -1 : 0);
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }

    static void sortArray(int[] a) {
        Random random = new Random();

        for (int i = 0; i < a.length; i++) {
            int randomPos = random.nextInt(a.length);
            int t = a[i];
            a[i] = a[randomPos];
            a[randomPos] = t;
        }
        Arrays.sort(a);
    }

    static final int MAX_VALUE = 1000000;

    public static void main(String[] args) throws FileNotFoundException {
//        InputReader in = new InputReader(new FileInputStream("input.txt"));
//        PrintWriter out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("milkvisits.out")));
//
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

//        long start = System.currentTimeMillis();
        String s = in.nextString();
        String p = in.nextString();

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


        int[] next = new int[n];
        for (int i = 0; i < n; i++) {
            next[i] = -1;
            if (s.charAt(i) == p.charAt(0)) {
                int k = 1;
                if (m == 1) {
                    next[i] = i + 1;
                } else {
                    for (int j = i + 1; j < n; j++) {
                        if (s.charAt(j) == p.charAt(k)) {
                            k++;
                            if (k == m) {
                                next[i] = j + 1;
                                break;
                            }
                        }
                    }
                }
            }
        }
        for (int i = maxK; i > 0; i--) {
            solve(i, 0, dp, s, p, next);
        }

        int[] ans = new int[n + 1];
        int best = 0;
        for (int i = 0; i <= maxK; i++) {
            int x = dp[i][0];
            if (x <= n) {
                ans[x] = Math.max(ans[x], i);
                best = i;
            }
        }
        int last = 0;
        int i = 0;
        for (; i <= n && ans[i] < best; i++) {
            ans[i] = Math.max(ans[i], last);
            last = Math.max(last, ans[i]);
        }


        for (; i <= n; i++) {
            if (best * m > n - i) {
                best -= 1;
            }
            ans[i] = best;
        }

        outputArray(ans, out, false);


        out.close();
    }

    private static void solve(int k, int x, int[][] dp, String s, String p, int[] next) {
        if (x == s.length() || dp[k][x] >= 0) {
            return;
        }
        int ans = MAX_VALUE;
        if (s.charAt(x) == p.charAt(0) && next[x] >= 0) {
            solve(k - 1, next[x], dp, s, p, next);
            ans = dp[k - 1][next[x]] + (next[x] - x - p.length());
        }
        solve(k, x + 1, dp, s, p, next);
        dp[k][x] = Math.min(ans, dp[k][x + 1]);
    }

    private static void outputArray(int[] ans, PrintWriter out, boolean addOne) {
        StringBuilder str = new StringBuilder();
        for (int j = 0; j < ans.length; j++) {
            long i = ans[j];
            long an = i + (addOne ? 1 : 0);
            str.append(an);
            if (j < ans.length- 1) {
                str.append(' ');
            }
        }
        out.println(str);
//        out.flush();
    }

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

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

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

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public String nextWord() {
            return next();
        }

        private List<Integer>[] readTree(int n) {
            return readGraph(n, n - 1);
        }

        private List<Integer>[] readGraph(int n, int m) {
            List<Integer>[] result = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                result[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                result[u].add(v);
                result[v].add(u);
            }
            return result;
        }

    }
}