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.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author karan173
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC
{
    char s[], p[];
    int n, m;
    int dp[][];
    int firstStart[];
    int INF = Integer.MAX_VALUE >> 1;
    public void solve(int testNumber, FastReader in, PrintWriter out)
    {
        s = in.ns ().toCharArray ();
        p = in.ns ().toCharArray ();
        n = s.length;
        m = p.length;
        firstStart = new int[n];
        Arrays.fill (firstStart, -1);
        for (int i = m - 1; i < n; i++)
        {
            firstStart[i] = getFirst (i);
        }
        int maxOverlappings = n / m;
        dp = new int[n + 1][maxOverlappings + 1];  //1 based
        Arrays.fill (dp[0], INF);
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= maxOverlappings; j++)
            {
                //dont use as end index
                dp[i][j] = dp[i - 1][j];
                //use as end index
                if (s[i - 1] == p[m - 1] && firstStart[i - 1] != -1 && j != 0)
                {
                    int k = firstStart[i - 1];
                    //[k, i-1] form a string
                    int toRemove = i - 1 - k + 1 - m;
                    dp[i][j] = Math.min (dp[i][j], dp[k][j - 1] + toRemove);
                }
            }
        }
        int ans[] = new int[n + 1];
        Arrays.fill (ans, 0);
        for (int overlap = 0; overlap <= maxOverlappings; overlap++)
        {
            int minRemove = dp[n][overlap];
            int maxRemove = n - overlap * m;
            minRemove = Math.max (minRemove, 0);
            maxRemove = Math.min (n, maxRemove);
            for (int j = minRemove; j <= maxRemove; j++)
            {
                ans[j] = Math.max (ans[j], overlap);
            }
        }
        for (int i = 0; i < n + 1; i++)
        {
            out.print (ans[i] + " ");
        }
        out.println ();

    }

    private int getFirst(int end)
    {
        int ctr = m - 1;
        while (ctr != -1 && end >= 0)
        {
            if (s[end] == p[ctr])
            {
                ctr--;
            }
            end--;
        }
        if (ctr == -1)
        {
            return end + 1;
        }
        return -1;
    }
}

class FastReader
{

    public InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream)
    {
        this.stream = stream;
    }

    public FastReader()
    {

    }

    public int read()
    {
        if (numChars == -1)
        {
            throw new InputMismatchException ();
        }
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read (buf);
            } catch (IOException e)
            {
                throw new InputMismatchException ();
            }
            if (numChars <= 0)
            {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public String ns()
    {
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        StringBuilder res = new StringBuilder ();
        do
        {
            res.appendCodePoint (c);
            c = read ();
        } while (!isSpaceChar (c));
        return res.toString ();
    }

    public boolean isSpaceChar(int c)
    {
        if (filter != null)
        {
            return filter.isSpaceChar (c);
        }
        return isWhitespace (c);
    }

    public static boolean isWhitespace(int c)
    {
        return c==' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}
