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.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class R272D2E {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String p = br.readLine();
        int n = s.length();
        int m = p.length();
        int[][] closest = new int[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++) closest[i][j]=-1;
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<=i && j<m; j++){
                if(i>0) closest[i][j]=closest[i-1][j];
                if(s.charAt(i)==p.charAt(j)){
                    if(j>0){
                        closest[i][j] = Math.max(closest[i][j], closest[i-1][j-1]);
                    } else{
                        closest[i][0] = i;
                    }
                }
            }
        }
//        for(int i=0; i<n; i++) System.out.print(closest[i][m-1]+" ");
        int[][] d = new int[n][n+1];
        for(int i=m-1; i<n; i++){
            for(int j=0; j<=i+1-m; j++){
                int closestIndex = closest[i][m-1];
                int deletableCount = i-closestIndex+1-m;
                if(closestIndex>=0 && deletableCount==j) d[i][j]=1;
                if(i>0) d[i][j] = Math.max(d[i][j], d[i-1][j]);
                if(j>0) d[i][j] = Math.max(d[i][j], d[i-1][j-1]);
                if(closestIndex>0 && j>=deletableCount){
                    d[i][j] = Math.max(d[i][j], d[closestIndex-1][j-deletableCount]+1);
                }
            }
        }
        for(int i=n-1; i<n; i++){
            for(int j=0; j<=n; j++){
                if(j==n) System.out.println(d[i][j]); else System.out.print(d[i][j]+" ");
            }
        }
    }
}
