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.awt.Dimension;

import java.io.*;
import static java.lang.Math.*;
import java.util.*;
//import java.math.BigInteger;
//import static java.lang.Character.*;
//import static java.lang.Math.*;
//import static java.math.BigInteger.*;
//import static java.util.Arrays.*;
//import java.awt.Point; // interger !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//import java.awt.Polygon;
//import java.awt.Rectangle;
//import java.awt.geom.AffineTransform;
//import java.awt.geom.Line2D;
//import java.awt.geom.Point2D;
//import javafx.scene.shape.Line;
//import javafx.scene.transform.Rotate;

//<editor-fold defaultstate="collapsed" desc="Main">
public class Ideone {
    // https://netbeans.org/kb/73/java/editor-codereference_ru.html#display

    private void run() {
        try {
            Locale.setDefault(Locale.US);
        } catch (Exception e) {
        }
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }

        if (oj) {
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException e) {
                MLE();
            }
        }
        Solver s = new Solver();
        s.sc = sc;
        s.out = out;
        s.solve();
        if (!oj) {
            err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
            err.printf("Mem: %d\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20);
        }
        out.flush();
    }

    private void show(int[] arr) {
        for (int v : arr) {
            err.print(" " + v);
        }
        err.println();
    }

    public static void exit() {
        err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
        err.printf("Mem: %d\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20);
        out.flush();
        out.close();
        System.exit(0);
    }

    public static void MLE() {
        int[][] arr = new int[1024 * 1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024 * 1024];
        }
    }

    public static void main(String[] args) {
        new Ideone().run();
    }

    static long timeBegin = System.currentTimeMillis();
    static FastScanner sc;
    static PrintWriter out;
    static PrintStream err = System.err;
}
    //</editor-fold>

//<editor-fold defaultstate="collapsed" desc="FastScanner">
class FastScanner {

    BufferedReader br;
    StringTokenizer st;

    FastScanner(InputStreamReader reader) {
        br = new BufferedReader(reader);
        st = new StringTokenizer("");
    }

    String next() {
        while (!st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception ex) {
                return null;
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        try {
            return br.readLine();
        } catch (IOException ex) {
            return null;
        }
    }
}
//</editor-fold>

class Solver {

    void aser(boolean OK) {
        if (!OK) {
            Ideone.MLE();
        }
    }

    FastScanner sc;
    PrintWriter out;
    static PrintStream err = System.err;

    char[] s, p;
    int[] prev;
    int[][] dp;
    
    void solve() {
        s = sc.next().toCharArray();
        p = sc.next().toCharArray();
        prev = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            int posS = i;
            boolean OK = true;
            for( int posB = p.length - 1; 0 <= posB; --posB ){
                while( 0 <= posS && s[posS] != p[posB] ) --posS;
                if( posS == -1 ){
                    OK = false;
                    break;
                }
                --posS;
            }
            if( OK ) prev[i] = posS + 1;
            else prev[i] = -1;
        }
        
        dp = new int[s.length][s.length+1];
        for (int pos = 0; pos < s.length; pos++) {
            for (int cntDel = 0; cntDel <= pos+1; cntDel++) {
                if( 0 <= pos-1 )
                    dp[pos][cntDel] = dp[pos-1][cntDel];
                if( prev[pos] != -1 ){
                    int cnt = pos-prev[pos]+1 - p.length;
                    if( 0 <= cntDel - cnt ){
                        int curDp = 1;
                        if (0 <= prev[pos] - 1) {
                            curDp += dp[prev[pos] - 1][cntDel - cnt];
                        }           
                        if( cntDel - cnt <= prev[pos]-1+1 )
                        if( 0 < prev[pos] || prev[pos]==0 && cntDel == cnt )
                            dp[pos][cntDel] = max( dp[pos][cntDel], curDp );
                    }
                }
            }
//            err.println( Arrays.toString(dp[pos]) );
        }
        
        for (int cntDel = 0; cntDel <= s.length; cntDel++) {
            out.print( " " + dp[s.length-1][cntDel] );
        }
        out.println();
    }

}