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

public class E {
    
    static String s;
    static String p;
    static int ls,lp,inf=99999999;
    static int[][] dp=new int[2010][2010];
    static int[] sv=new int[2010];
    
    static int find(int ind)
    {
        int i,j=0,cnt=0;
        for(i=ind;i<ls;i++)
        {
            if(s.charAt(i)==p.charAt(j))
            {
                j++;
                if(j==lp)
                    return cnt;
            }
            else
                cnt++;
        }
        return -1;
    }
    
    static int rec(int ind,int x)
    {
        if(ind>=ls)
        {
            if(x==0)
                return 0;
            return -inf;
        }
        
        if(x<0)
            return -inf;
        if(dp[ind][x]!=-1)
            return dp[ind][x];
        
        dp[ind][x]=rec(ind+1,x);
        int p1=rec(ind+1,x-1);
        if(p1>dp[ind][x])
            dp[ind][x]=p1;
        if(s.charAt(ind)==p.charAt(0)&&sv[ind]!=-1)
            p1=1+rec(ind+sv[ind]+lp,x-sv[ind]);
        if(p1>dp[ind][x])
            dp[ind][x]=p1;
        return dp[ind][x];
    }
    
    public static void main(String[] args) {
        
        Scanner sc=new Scanner(System.in);
        
        while(sc.hasNext())
        {
            s=sc.next();
            p=sc.next();
            
            ls=s.length();
            lp=p.length();
            
            int i,j;
            for(i=0;i<ls;i++)
            {
                for(j=0;j<ls;j++)
                    dp[i][j]=-1;
            }
            
            for(i=0;i<ls;i++)
            {
                sv[i]=find(i);
            }
            
            for(i=0;i<=ls;i++)
            {
                int ans=rec(0,i);
                System.out.print(ans+" ");
            }
            System.out.println("");
        }
    }
}