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.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        String S = in.next();
        String P = in.next();
        int[][] dp = new int[S.length()+10][S.length()+10];
        int[] a = new int[S.length()];
        for(int i=0; i<S.length(); ++i){
            int jS = i;
            int jP = 0;
            while(jP < P.length()){
                while(jS < S.length() && S.charAt(jS) != P.charAt(jP)) ++jS;
                while(jS < S.length() && jP < P.length() && P.charAt(jP) == S.charAt(jS)){
                    ++jS;
                    ++jP;
                }
                if (jS == S.length()) break;
            }
            
            if (jP == P.length()) a[i] = jS - i;
            //out.println(i + " " + a[i]);
        }
        
        for(int i=0; i<S.length(); ++i){
            for(int j=0; j<=i; ++j){
                dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]);
                if (a[i] != 0) dp[i+a[i]][j+(a[i]-P.length())] = max(dp[i+a[i]][j+(a[i]-P.length())], dp[i][j] + 1);
            }
        }
        
        
        for(int i=0; i<=S.length(); ++i){
            out.print(dp[S.length()][i] + " ");
        }
    }

    private int max(int i, int j) {
        
        if (i < j ) return j;
        return i;
    }
}

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 long nextLong() {
        return Long.parseLong(next());
    }

}