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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Map;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.Iterator;
import java.util.Set;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.AbstractMap;
import java.util.TreeMap;
import java.io.Closeable;
import java.io.Writer;
import java.util.Map.Entry;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CDreamoonAndStrings solver = new CDreamoonAndStrings();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CDreamoonAndStrings {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            char[] s = in.rs().toCharArray();
            char[] p = in.rs().toCharArray();
            int n = s.length;
            int m = p.length;
            int[] prev = new int[n + 1];
            int[] next = new int[n + 1];
            int inf = (int) 1e9;
            Arrays.fill(prev, inf);
            prev[0] = 0;
            for (char c : s) {
                Arrays.fill(next, inf);
                for (int i = 0, iModM = 0; i <= n; i++, iModM++) {
                    if (iModM == m) {
                        iModM = 0;
                    }
                    //give up
                    next[i] = Math.min(next[i], prev[i] + Integer.signum(iModM));

                    if (p[iModM] == c && i + 1 <= n) {
                        next[i + 1] = Math.min(next[i + 1], prev[i]);
                    }
                }
                int[] tmp = prev;
                prev = next;
                next = tmp;
            }
            MonotoneOrderBeta<Integer, Integer> mo = new MonotoneOrderBeta<Integer, Integer>(Comparator.naturalOrder(), Comparator.naturalOrder(),
                    true, true);
            mo.add(0, 0);
            for (int i = 0; i <= n; i++) {
                mo.add(prev[i], i / m);
            }
            for (int i = 0; i <= n; i++) {
                int floor = mo.floor(i);
                floor = Math.min(floor, (n - i) / m);
                out.println(floor);
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public String rs() {
            return readString();
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }

    static class MonotoneOrderBeta<K, V> implements Iterable<Map.Entry<K, V>> {
        TreeMap<K, V> map;
        Comparator<V> vComp;
        boolean preferLarger;

        public MonotoneOrderBeta(Comparator<K> keyComp, Comparator<V> valueComp, boolean inc, boolean preferLarger) {
            map = new TreeMap<>(keyComp);
            if (!inc) {
                vComp = valueComp.reversed();
                preferLarger = !preferLarger;
            } else {
                vComp = valueComp;
            }
            this.preferLarger = preferLarger;
        }

        public void add(K k, V v) {
            if (preferLarger) {
                Map.Entry<K, V> floor = map.floorEntry(k);
                if (floor != null && vComp.compare(floor.getValue(), v) >= 0) {
                    return;
                }
                while (true) {
                    Map.Entry<K, V> ceil = map.ceilingEntry(k);
                    if (ceil == null || vComp.compare(v, ceil.getValue()) < 0) {
                        break;
                    }
                    map.remove(ceil.getKey());
                }
            } else {
                Map.Entry<K, V> ceil = map.ceilingEntry(k);
                if (ceil != null && vComp.compare(v, ceil.getValue()) >= 0) {
                    return;
                }
                while (true) {
                    Map.Entry<K, V> floor = map.floorEntry(k);
                    if (floor == null || vComp.compare(floor.getValue(), v) < 0) {
                        break;
                    }
                    map.remove(floor.getKey());
                }
            }
            map.put(k, v);
        }

        public V floor(K k) {
            Map.Entry<K, V> entry = map.floorEntry(k);
            return entry == null ? null : entry.getValue();
        }

        public Iterator<Map.Entry<K, V>> iterator() {
            return map.entrySet().iterator();
        }

        public String toString() {
            return map.toString();
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}

