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.util.Arrays;
import java.util.ArrayList;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.List;
import java.io.BufferedReader;
import java.math.BigInteger;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Comparator;
import java.io.IOException;
import java.util.StringTokenizer;

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

class TaskC {
    Scanner in;
    PrintWriter out;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        this.in = in;
        this.out = out;
        run();
    }

    void run() {
        char[] s = in.next().toCharArray();
        char[] p = in.next().toCharArray();
        int n = s.length;
        int m = p.length;
        int[] id = new int[n];
        Arrays.fill(id, -1);
        int cnt = 0;
        for (int i = 0, crt = 0; i < n; i++) {
            id[i] = cnt;
            if (s[i] == p[crt]) {
                crt++;
                if (crt == m) {
                    cnt++;
                    crt = 0;
                }
            }
        }
        List<P> ps = new ArrayList<P>();
        for (int i = 0; i < n; i++) {
            if (s[i] == p[0]) {
                int x = i;
                int y = i;
                int crt = 0;
                for (; crt < m; crt++) {
                    while (y < n && s[y] != p[crt]) y++;
                    if (y == n) break;
                    y++;
                }
                if (crt == m) {
                    ps.add(new P(x, y - 1));
                }
            }
        }
        int pn = ps.size();
        int[] is = new int[cnt];
        int[][] dp = new int[cnt][pn];
//        Algo.debug(ps);
        int[][] dp2 = new int[cnt][pn];
        Algo.fill(dp, 12341234);
        int[][] pre = new int[cnt][pn];
        Algo.fill(pre, -1);
        for (int i = 0; i < pn; i++) {
            dp[0][i] = ps.get(i).y - ps.get(i).x + 1;
            dp2[0][i] = i;
            if (i > 0) {
                if (dp[0][i] > dp[0][i - 1]) {
                    dp[0][i] = dp[0][i - 1];
                    dp2[0][i] = dp2[0][i - 1];
                }
            }
        }
        for (int i = 1; i < cnt; i++) {
            int gid = 0;
            for (int j = i, g = 0; j < pn; j++) {
//                while (ps.get(g).y < ps.get(j).x) {
//                    if (dp[i - 1][gid] > dp[i - 1][g]) gid = g;
//                    g++;
//                }
                int up = Algo.lowerBound(ps, new P(0, ps.get(j).x)) - 1;
                if (up >= 0) {
                    dp[i][j] = dp[i - 1][up] + ps.get(j).y - ps.get(j).x + 1;
                    dp2[i][j] = j;
                    pre[i][j] = up;
                }
                if (j > 0) {
                    if (dp[i][j] > dp[i][j - 1]) {
                        dp[i][j] = dp[i][j - 1];
                        dp2[i][j] = dp2[i][j - 1];
                    }
                }
//                for (int k = 0; ps.get(k).y < ps.get(j).x; k++) {
//                    int tmp = dp[i - 1][k] + ps.get(j).y - ps.get(j).x + 1;
//                    if (tmp < dp[i][j]) {
//                        dp[i][j] = tmp;
//                        pre[i][j] = k;
//                    }
//                }
            }
        }
//        Algo.debug(cnt, dp[cnt - 1]);
        int first = 0;
        for (int i = 0; i < pn; i++) {
            if (dp[cnt - 1][i] < dp[cnt - 1][first]) first = i;
        }
        for (int i = cnt - 1; i >= 0; i--) {
            first = dp2[i][first];
            is[i] = ps.get(first).y - ps.get(first).x + 1;
            first = pre[i][first];
        }
        int[] ans = new int[n + 1];
        for (int i = 1; i <= cnt * m; i++) {
            ans[i] = i / m;
        }
        Arrays.sort(is);
        int sum = (int) Algo.sum(is);
        int delta = sum - cnt * m;
        for (int i = cnt * m; i <= n - delta; i++) {
            ans[i] = cnt;
        }
        for (int i = 0; i < cnt; i++) is[i] -= m;
//        Algo.debug(is);
        for (int i = 0, crt = n; i < cnt; i++) {
            int val = calc(dp, dp2, pre, ps, pn, i + 1) - m * (i + 1);
//            Algo.debug(i, val);
            while (n - crt < val) {
                ans[crt--] = i;
            }
        }
        for (int i = n; i >= 0; i--) {
            out.print(ans[i] + " ");
        }
        out.println();
    }

    private int calc(int[][] dp, int[][] dp2, int[][] pre, List<P> ps, int pn, int cnt) {
        int first = 0;
        for (int i = 0; i < pn; i++) {
            if (dp[cnt - 1][i] < dp[cnt - 1][first]) first = i;
        }
        int sum = 0;
        for (int i = cnt - 1; i >= 0; i--) {
            first = dp2[i][first];
            sum += ps.get(first).y - ps.get(first).x + 1;
            first = pre[i][first];
        }
        return sum;
    }

    class P implements Comparable<P> {
        int x;
        int y;

        P(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int compareTo(P o) {
            return y - o.y;
        }

        public String toString() {
            return "P{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}

class Scanner {
    BufferedReader br;
    StringTokenizer st;

    public Scanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in));
        eat("");
    }

    private void eat(String s) {
        st = new StringTokenizer(s);
    }

    public String nextLine() {
        try {
            return br.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public boolean hasNext() {
        while (!st.hasMoreTokens()) {
            String s = nextLine();
            if (s == null)
                return false;
            eat(s);
        }
        return true;
    }

    public String next() {
        hasNext();
        return st.nextToken();
    }

}

class Algo {


    public static long sum(int[] is) {
        long res = 0;
        for (int i = 0; i < is.length; i++) {
            res += is[i];
        }
        return res;
    }

    public static <T extends Comparable<T>> int lowerBound(List<T> tl, T v) {
        return lowerBound(tl, 0, tl.size(), v);
    }

    public static<T extends Comparable<T>> int lowerBound(List<T> tl, int l, int r, T v) {
        while (l < r) {
            int m = (l + r) >> 1;
            if (tl.get(m).compareTo(v) >= 0) r = m;
            else l = m + 1;
        }
        return l;
    }

    public static void fill(int[][] iss, int v) {
        for (int[] is : iss) Arrays.fill(is, v);
    }

}

