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.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static final int INF = 1<<29;
	public static void main(String[] args) {
		IO io = new IO();
		char[] s = io.next().toCharArray();
		char[] p = io.next().toCharArray();
		int n = s.length;
		int m = p.length;
		ArrayList<Pair> a = new ArrayList<>();
		for(int i=0;i<n;i++) {
			int k = 0;
			for(int j=i;j<n;j++) {
				if (s[j] == p[k]) {
					k++;
					if (k == m) {
						a.add(new Pair(i,j));
						break;
					}
				}
			}
		}
		int l = a.size();
		int[][] dp = new int[l+1][l+1];
		for(int i=0;i<=l;i++) {
			for(int j=1;j<=l;j++) {
				dp[i][j] = INF;
			}
		}
		dp[0][0] = 0;
		for(int i=1;i<=l;i++) {
			int i_ = 0;
			for(int j=i-1;j>=1;j--) {
				if (a.get(j-1).b < a.get(i-1).a) {
					i_ = j;
					break;
				}
			}
			for(int j=1;j<=l;j++) {
				dp[i][j] = Math.min(dp[i-1][j], dp[i_][j-1] + (a.get(i-1).b - a.get(i-1).a + 1));
			}
		}
		int max = -1;
		for(int i=0;i<=l;i++) {
			if (dp[l][i] < INF) {
				max = i;
			}
		}
		int[] ansrev = new int[n+1];
		for(int i=0;i<=n;i++) {
			if (i <= max * m) {
				ansrev[i] = i / m;
			}else{
				for(int j=0;j<=l;j++) {
					if (i <= j * m + (n - dp[l][j])) {
						ansrev[i] = j;
					}else{
						break;
					}
				}
			}
		}
		for(int i=n;i>=0;i--) {
			if (i < n) {
				io.print(" ");
			}
			io.print(ansrev[i]);
		}
		io.flush();
	}
	
	static class Pair {
		int a,b;
		public Pair(int a,int b) {
			this.a = a;
			this.b = b;
		}
	}

}
class IO {
	BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder out = new StringBuilder();
	int index = 0;
	String bfl = null;
	String[] bf = new String[0];
	private boolean read() {
		try {
			bfl = bi.readLine();
			if (bfl == null) {
				return false;
			}
			bf = bfl.split("\\s");
			index = 0;
		} catch (IOException e) {
			e.printStackTrace();
		}
		return true;
	}
	public boolean hasNext() { return index < bf.length ? true : read(); }
	public boolean hasNextLine() { return read(); }
	public String next() { return hasNext() ? bf[index++] : null; }
	public String nextLine() { return hasNextLine() ? bfl : null; }
	public int nextInt() { return Integer.parseInt(next()); }
	public long nextLong() { return Long.parseLong(next()); }
	public double nextDouble() { return Double.parseDouble(next()); };
	public void println(long x) { out.append(x); out.append("\n"); }
	public void println(double x) { out.append(x); out.append("\n"); }
	public void println(String s) { out.append(s); out.append("\n"); }
	public void print(long x) { out.append(x); }
	public void print(double x) { out.append(x); }
	public void print(String s) { out.append(s); }
	public void flush() {System.out.print(out); out = new StringBuilder(); }
	public int[] arrayInt(int n) {
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = nextInt();
		}
		return a;
	}
	public long[] arrayLong(int n) {
		long[] a = new long[n];
		for(int i=0;i<n;i++) {
			a[i] = nextLong();
		}
		return a;
	}
	public double[] arrayDouble(int n) {
		double[] a = new double[n];
		for(int i=0;i<n;i++) {
			a[i] = nextDouble();
		}
		return a;
	}
}
