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.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
public class A {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        String p = bf.readLine();
        double[][] dist = new double[s.length()+1][s.length()/p.length()*p.length()+1];
        for(int i=0; i<dist.length; i++) Arrays.fill(dist[i], Double.POSITIVE_INFINITY);
        for(int i=0; i<dist.length; i++) dist[i][0] = 0;
        if(s.charAt(0) == p.charAt(0)) dist[0][0] = 0;
        for(int i=1; i<=s.length(); i++) {
            for(int j=1; j<=s.length()/p.length()*p.length(); j++) {
                if(s.charAt(i-1) == p.charAt((j-1) % p.length())) 
                    dist[i][j] = dist[i-1][j-1];
                if(j % p.length() == 0) dist[i][j] = Math.min(dist[i][j], dist[i-1][j]);
                else dist[i][j] =  Math.min(dist[i][j],dist[i-1][j]+1);
            }
        }
        // for(int i=0; i<dist.length; i++) System.out.println(Arrays.toString(dist[i]));
        if(p.length() > s.length()) {
            for(int i=0; i<s.length() + 1; i++)
                System.out.print("0 ");
            System.exit(0);
        }
        int[] ans = new int[s.length()]; int counter = p.length(); int marker2 = (int)dist[s.length()][counter];
        boolean n = false;
        for(int i=0; i<s.length(); i++) {
            //System.out.println(counter + " " + marker2);
            int next = counter + p.length();
            if(counter >= dist[0].length || dist[s.length()][counter] == Double.POSITIVE_INFINITY) 
                break;
            else{
                // System.out.println(counter/p.length() + " " + (s.length() - marker2)/p.length());
                for(marker2 = (int)dist[s.length()][counter]; next < dist[0].length && marker2<dist[s.length()][next] && marker2<s.length(); marker2++)
                    ans[marker2] = Math.min(counter/p.length(),  (s.length() - marker2)/p.length());
                // System.out.println(Arrays.toString(ans) + " " + marker2);
            }
            counter += p.length();
            
        }
        while(marker2 < s.length()) {
            ans[marker2] = (s.length() - marker2)/p.length();
            marker2++;
            // System.out.println("hi");
        }
        for(int i=0; i<ans.length; i++) System.out.print(ans[i] + " ");
        System.out.println("0");
        
        // Scanner scan = new Scanner(System.in);
        // PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 
        // int n = Integer.parseInt(bf.readLine());
        // StringTokenizer st = new StringTokenizer(bf.readLine());
        // int[] a = new int[n]; for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        // int n = Integer.parseInt(st.nextToken());
        // int n = scan.nextInt();
        
        // out.close(); System.exit(0);
    }
}