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.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class E {
	static int[] endsWhere;
	static String p;
	static int[][] dp;

	public static int solve(int idx, int rem) {
		if (idx == dp.length) {
			if (rem == 0)
				return 0;
			return -1000000;
		}
		if (dp[idx][rem] != -1)
			return dp[idx][rem];
		int res;
		if (rem > 0)
			res = Math.max(solve(idx + 1, rem), solve(idx + 1, rem - 1));
		else
			res = solve(idx + 1, rem);
		if (endsWhere[idx] != -1) {
			int needed = (endsWhere[idx] - idx + 1 - p.length());
			if (needed <= rem) {
				res = Math
						.max(res, 1 + solve(endsWhere[idx] + 1, rem - needed));
			}
		}
		return dp[idx][rem] = res;
	}

	public static void main(String[] args) throws Exception {
		String str = next();
		p = next();
		int[] last = new int[26];
		int[][] next = new int[str.length()][26];
		for (int i = str.length() - 1; i >= 0; i--) {
			for (int j = 0; j < 26; j++) {
				next[i][j] = last[j];
			}
			last[str.charAt(i) - 'a'] = i;
		}
		endsWhere = new int[str.length()];
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) != p.charAt(0)) {
				endsWhere[i] = -1;
				continue;
			}
			int lastIdx = i;
			boolean found = true;
			for (int j = 1; j < p.length(); j++) {
				lastIdx = next[lastIdx][p.charAt(j) - 'a'];
				if (lastIdx == 0) {
					found = false;
					break;
				}
			}
			if (!found) {
				endsWhere[i] = -1;
			} else {
				endsWhere[i] = lastIdx;
			}
		}
		dp = new int[str.length()][str.length() + 1];
		for (int i = 0; i < str.length(); i++) {
			Arrays.fill(dp[i], -1);
		}
		PrintWriter out = new PrintWriter(System.out);
		for (int i = 0; i <= str.length(); i++) {
			out.print(solve(0, i) + " ");
		}
		out.flush();
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(
			System.in));
	static StringTokenizer tokenizer = new StringTokenizer("");

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

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

	static String next() throws Exception {
		while (true) {
			if (tokenizer.hasMoreTokens()) {
				return tokenizer.nextToken();
			}
			String s = br.readLine();
			if (s == null) {
				return null;
			}
			tokenizer = new StringTokenizer(s);
		}
	}
}
