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;

/**
 * 476E
 * O(|s|^2 + |p|) time
 * θ(|s| + |p|) space
 *
 * @author artyom
 */
public class _476E implements Runnable {
    private BufferedReader in;

    private Object solve() throws IOException {
        String s = nextToken(), p = nextToken();
        int n = s.length(), m = p.length();
        int[] len = new int[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == p.charAt(0)) {
                for (int j = i, c = 0; j <= n - m + c; j++) {
                    if (s.charAt(j) == p.charAt(c)) {
                        if (++c == m) {
                            len[i] = j - i + 1;
                            break;
                        }
                    }
                }
            }
        }
        int[] sd = new int[n + 1];
        StringBuilder sb = new StringBuilder();
        int c = 0, r = 0;
        while (true) {
            int[] dp = new int[n + 1];
            for (int i = n - 1; i >= 0; i--) {
                if (len[i] > 0) {
                    if (sd[i + len[i]] >= c) {
                        dp[i] = dp[i + 1] == 0 ? len[i] + sd[i + len[i]] : Math.min(dp[i + 1], len[i] + sd[i + len[i]]);
                    }
                } else {
                    dp[i] = dp[i + 1];
                }
            }
            if (dp[0] == 0) {
                break;
            }
            int k = dp[0] - m * (c + 1) - r;
            for (int i = 0; i < k; i++) {
                sb.append(c).append(' ');
            }
            sd = dp;
            r += k;
            c++;
        }
        int k = n - r - c * m;
        for (int i = 0; i <= k; i++) {
            sb.append(c).append(' ');
        }
        while (--c >= 0) {
            for (int i = 0; i < m; i++) {
                sb.append(c).append(' ');
            }
        }
        return sb;
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new _476E().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            System.out.print(solve());
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        return in.readLine();
    }
}