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.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class C {

    static void solve() throws IOException {
        char[] s = in.next().toCharArray();
        char[] p = in.next().toCharArray();
        int[][] r = new int[s.length + 1][s.length + 1];
        for ( int i = 0; i < s.length; i ++ ) {
            int k = 0;
            int cur = 0;
            for ( int j = i; j < s.length && cur < p.length; j ++ ) {
                if ( p[cur] == s[j] ) {
                    cur ++;
                } else {
                    k ++;
                }
            }
            if ( cur < p.length ) {
                k = -1;
            }
            for ( int j = 0; j <= i; j ++ ) {
                r[i + 1][j] = Math.max( r[i + 1][j], r[i][j] );
                r[i + 1][j + 1] = Math.max( r[i + 1][j + 1], r[i][j] );
                if ( k >= 0 ) {
                    r[i + p.length + k][j + k] = Math.max( r[i + p.length + k][j + k], r[i][j] + 1 );
                }
            }
        }
        for ( int j = 0; j <= s.length; j ++ ) {
            out.print( r[s.length][j] + " " );
        }
        out.println();
    }

    static Scanner in;
//    static StreamTokenizer in;
    static PrintWriter out;

//    static int nextInt() throws IOException {
//        in.nextToken();
//        return ( int ) in.nval;
//    }

    public static void main( String[] args ) throws IOException {
        in = new Scanner( System.in );
//        in = new StreamTokenizer( new InputStreamReader( System.in ) );
        out = new PrintWriter( System.out );
        solve();
        out.close();
    }
}
