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.StringTokenizer;


public class E476 {
    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;
    
    int [] A ;
    int [][] dp;
    String a;
    String b;
    public String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }

        return in.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    
    public void solve() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        
        a = nextToken();
        b = nextToken();
        
        boolean [][] appears = new boolean[a.length()][b.length()];
        
        for(int i = 0 ; i < b.length(); i++)
            for(int j = 0 ; j < a.length(); j++) {
                if(b.charAt(i) == a.charAt(j)) {
                    appears[j][i] = true;
                }
            }
        
        A = new int[a.length()];
        dp = new int[a.length()+1][a.length()+1];
        for(int i = 0 ; i < dp.length; i++)
            for(int j = 0 ; j < dp.length; j++) {
                    dp[i][j] = Integer.MIN_VALUE;
            }

        for(int i = 0 ; i < a.length(); i++) {
            A[i] = -1;
            if(appears[i][0]) {
                int count = 1;
                int j = i + 1;
                for(; j<a.length() && count < b.length(); j++) {
                    if(appears[j][count])
                        count++;
                }
                if(count == b.length())
                    A[i] = j - i - b.length();
            }
        }
        
  //      for(int i = 0 ; i < a.length(); i++)
   //       out.print(A[i]+" ");
    //    out.println();
        for(int i = 0 ; i <= a.length(); i++)
            out.print(fillTable(i,0)+" ");
        out.println();
   //     for(int i = 0 ; i < dp.length; i++,out.println())
    //      for(int j = 0 ; j < dp.length; j++)
     //         out.print(dp[i][j]+" ");
        out.close();
        
    }
    
    public int fillTable(int k, int i) {
        if(k < 0)
            return -1000000;
        if(i == a.length() && k == 0)
            return 0;
        if(i >= a.length() && k > 0)
            return -1000000;

        if(dp[k][i] != Integer.MIN_VALUE)
            return dp[k][i];
        
        int val1 = Integer.MIN_VALUE;
        int val2 = Integer.MIN_VALUE;
        int val3 = Integer.MIN_VALUE;
        if(A[i] != -1) {
            val1  = 1 + fillTable(k - A[i], i + A[i] + b.length());
        }
        val2 = fillTable(k, i+1);
        val3 = fillTable(k-1, i+1);
        
        dp[k][i] = Math.max(val1, Math.max(val2,val3));
        return dp[k][i];
    }
    
    public static void main (String [] args) throws IOException {
        new E476().solve();
    }
}
