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.*;
public class C {
    public static long time = 0;
    public static void main(String[] args) throws Exception {
        time = System.currentTimeMillis();
        
        IN = System.in;
        OUT = System.out;
        in = new BufferedReader(new InputStreamReader(IN));
        out = new PrintWriter(OUT, FLUSH);
        solveOne();
        out.flush();
    }
    static long MOD = (long) (1e9) + 7l;
    public static void solveOne() throws Exception {
        char[] s = nx().toCharArray();
        char[] p = nx().toCharArray();
        
        int[] shortestFrom = new int[s.length];
        Arrays.fill(shortestFrom, Integer.MAX_VALUE);
        for (int start = 0; start < s.length; start++){
            int matchPtr = 0;
            for (int ptr = start; ptr < s.length; ptr++){
                if (p[matchPtr] == s[ptr]){
                    if (matchPtr == p.length - 1){
                        int curLength = ptr + 1 - start;
                        if (curLength < shortestFrom[start]){
                            shortestFrom[start] = curLength;
                        }
//                      shortestFrom[start] = Math.min(shortestFrom[start], curLength);
                        break;
                    }
                    else {
                        matchPtr++;
                    }
                }
                
//              if (curLength < shortestList[whole]){
//                  shortestList[whole] = curLength;;
//              }
                
            }
        }
        int[][] dp = new int[s.length + 1][s.length + 5];
        for (int[] e: dp) Arrays.fill(e, Integer.MAX_VALUE);
        dp[0][0] = 0;
        for (int i = 0 ; i < s.length; i++){
            if (i > 0){
                for (int j = 0; j < s.length + 5; j++){
                    if (dp[i - 1][j] < dp[i][j])
                    dp[i][j] = dp[i - 1][j];
                }
            }
            
            if (shortestFrom[i] == Integer.MAX_VALUE) continue;
            int curPenality = shortestFrom[i] - p.length;
            int end = i + shortestFrom[i];
            for (int j = 0;j < s.length + 5 - 1; j++){
                if (dp[i][j] == Integer.MAX_VALUE) continue;
                int newValue = dp[i][j] + curPenality;
                if (newValue < dp[end][j + 1]) dp[end][j + 1] = newValue;
            }
        }
        
        int[] shortestList = new int[s.length + 5];
        Arrays.fill(shortestList, Integer.MAX_VALUE);
        shortestList[0] = 0;
        for (int[] e: dp){
            for (int i = 0 ; i < e.length; i++){
                if (e[i] < shortestList[i]){
                    shortestList[i] = e[i];
                }
            }
        }
        
//      px(shortestList);
        int canPtr = 0;
        for (int i = 0; i <= s.length; i++){
            for (;canPtr < shortestList.length;){
                if (shortestList[canPtr + 1] == Integer.MAX_VALUE) break;
                int bestRemoval = shortestList[canPtr + 1];
                if (bestRemoval <= i){
                    canPtr++;
                }
                else break;
            }
//          px(i, canPtr);
            if (i != 0) p (" ");
            p(Math.min(canPtr, (s.length - i) / p.length) );
        }
    }
    
    public static void solveTwo() throws Exception {
        
    }
    
    public static void solveThree() throws Exception {
        
    }
    
    public static BufferedReader in;
    public static StringTokenizer st;
    public static InputStream IN;
    public static OutputStream OUT;
    public static String nx() throws Exception {
        for (;st == null || !st.hasMoreTokens();){
            String k1 = in.readLine();
            if (k1 == null) return null;
            st = new StringTokenizer(k1);
        }
        return st.nextToken();
    }
    public static int ni () throws Exception {
        return Integer.parseInt(nx());
    }
    public static long nl() throws Exception{
        return Long.parseLong(nx());
    }
    public static double nd() throws Exception{
        return Double.parseDouble(nx());
    }
    public static void px(Object ... l1){
        System.out.println(Arrays.deepToString(l1));
    }
    public static boolean FLUSH = false;
    public static PrintWriter out;
    public static void p(Object ... l1){
        for (int i = 0; i < l1.length; i++){
            if (i != 0) out.print(' ');
            out.print(l1[i].toString());
        }
    }
    public static void pn(Object ... l1){
        for (int i = 0; i < l1.length; i++){
            if (i != 0) out.print(' ');
            out.print(l1[i].toString());
        }
        out.println();
    }
    
    public static void pn(Collection l1){
        boolean first = true;
        for (Object e: l1){
            if (first) first = false;
            else out.print(' ');
            out.print(e.toString());
        }
        out.println();
    }

}
