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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Solution {
    private static int[] prefixFunction(char[] s) {
        int[] pi = new int[s.length + 1];
        for (int length = 2; length <= s.length; length++) {
            int k = pi[length - 1];
            while (k > 0 && s[length - 1] != s[k]) {
                k = pi[k];
            }
            if (s[length - 1] == s[k]) {
                k++;
            }
            pi[length] = k;
        }
        return pi;
    }

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
             PrintWriter writer = new PrintWriter(System.out)) {
            char[] s = next(reader).toCharArray();
            char[] p = next(reader).toCharArray();
            int[] pi = prefixFunction(p);
            int[][] dp = new int[s.length + 1][s.length + 1];
            for (int[] row : dp) {
                Arrays.fill(row, Integer.MAX_VALUE);
            }
            int[][] positions = new int[26][s.length + 1];
            for (char ch = 'a'; ch <= 'z'; ch++) {
                int ci = ch - 'a';
                positions[ci][s.length] = s.length;
                for (int i = s.length - 1; i >= 0; i--) {
                    positions[ci][i] = positions[ci][i + 1];
                    if (s[i] == ch) {
                        positions[ci][i] = i;
                    }
                }
            }
            dp[0][0] = 0;
            for (int l = 0; l < s.length; l++) {
                for (int k = 0; k * p.length < s.length; k++) {
                    int base = k * p.length;
                    for (int r = 0; r < p.length && base + r < s.length; r++) {
                        if (dp[l][base + r] == Integer.MAX_VALUE) {
                            continue;
                        }
                        dp[l + 1][base + r] = Math.min(dp[l + 1][base + r], dp[l][base + r] + 1);
                        for (char ch = 'a'; ch <= 'z'; ch++) {
                            int chPos = positions[ch - 'a'][l];
                            if (chPos < s.length) {
                                int newR = r;
                                while (newR > 0 && p[newR] != ch) {
                                    newR = pi[newR];
                                }
                                if (p[newR] == ch) {
                                    newR++;
                                }
                                dp[chPos + 1][base + newR] = Math.min(dp[chPos + 1][base + newR], dp[l][base + r] + chPos - l);
                            }
                        }
                    }
                }
            }
            int[] answer = new int[s.length + 1];
            for (int k = 1; k * p.length <= s.length; k++) {
                int base = k * p.length;
                for (int r = 0; r < p.length && base + r <= s.length; r++) {
                    if (dp[s.length][base + r] == Integer.MAX_VALUE) {
                        continue;
                    }
                    int maxSkip = s.length - base;
                    int minSkip = dp[s.length][base + r];
                    for (int i = minSkip; i <= maxSkip; i++) {
                        answer[i] = Math.max(answer[i], k);
                    }
                }
            }
            for (int x : answer) {
                writer.print(x + " ");
            }
        }
    }

    private static StringTokenizer stringTokenizer;

    private static String next(BufferedReader reader) throws IOException {
        if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(reader.readLine());
        }
        return stringTokenizer.nextToken();
    }

    private static int nextInt(BufferedReader reader) throws IOException {
        return Integer.parseInt(next(reader));
    }

    private static long nextLong(BufferedReader reader) throws IOException {
        return Long.parseLong(next(reader));
    }
}
