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.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class main3 {

	static boolean[][] ce;
	static int[][] c;
	static int[][] cm;
	static boolean[] cme;
	static int solve(char[] s, char[] p, int pos, int x) {
		if (s.length - pos == x) {
			return 0;
		}
		
		if (s.length - pos < x)
			return -1;
		
		if(ce[pos][x]) {
			return c[pos][x];
		}

		int ans1 = solve(s, p, pos + 1, x);

		int ans2 = 0;
		if (x > 0)
			ans2 = solve(s, p, pos + 1, x - 1);

		int ans3 = 0;
		if (p[0] == s[pos]) {
			int[] m = getMatch(s, p, pos);
			if (m != null && x >= m[1]) {
				ans3 = solve(s, p, pos + p.length + m[1], x - m[1]);
				if (ans3 >= 0)
					ans3++;
				else
					ans3 = 0;
			}
		}

		int finalAns = Math.max(Math.max(ans1, ans2), ans3);
		
		ce[pos][x] = true;
		c[pos][x] = finalAns;
		
		return finalAns;
	}

	static List<List<Integer>> matchCache;

	static int[] getMatch(char[] s, char[] p, int pos) {
		if (cme[pos])
		{
			if (cm[pos] == null)
				return null;
			else
				return new int[] { cm[pos][0], cm[pos][1]};
		}
		
		int cp = 1;
		int origPos = pos;
		pos++;
		int letGo = 0;
		while (cp < p.length && pos < s.length) {
			if (s[pos] == p[cp]) {
				cp++;
				pos++;
			} else {
				letGo++;
				pos++;
			}
		}

		int[] ans = null;
		if (cp == p.length) {
			ans = new int[] { origPos, letGo };
		}
		
		cm[origPos] = ans;
		cme[origPos] = true;
		
		if (ans == null)
			return null;
		else {
			return new int[] {ans[0], ans[1]};
		}
	}

	static List<Integer> bestMatches(char[] s, char[] p, int pos) {

		if (pos >= s.length) {
			return null;
		}

		if (matchCache.get(pos) != null)
			return new ArrayList<Integer>(matchCache.get(pos));

		List<Integer> ans1 = bestMatches(s, p, pos + 1);

		List<Integer> ans2 = null;
		if (s[pos] == p[0]) {
			int[] match = getMatch(s, p, pos);
			if (match != null) {
				ans2 = bestMatches(s, p, pos + p.length + match[1]);
				if (ans2 == null) {
					ans2 = new ArrayList<Integer>();
				}

				ans2.add(match[1]);
			}
		}

		List<Integer> finalAns = null;
		if (ans1 == null && ans2 == null) {

		} else if (ans1 != null && ans2 == null) {
			finalAns = new ArrayList<Integer>(ans1);
		} else if (ans1 == null && ans2 != null) {
			finalAns = new ArrayList<Integer>(ans2);
		} else {
			if (ans1.size() > ans2.size()) {
				finalAns = ans1;
			} else if (ans1.size() < ans2.size()) {
				finalAns = ans2;
			} else {
				int as = 0;
				for (Integer v : ans1) {
					as += v;
				}

				int bs = 0;
				for (Integer v : ans2) {
					bs += v;
				}

				if (as < bs) {
					finalAns = ans1;
				} else {
					finalAns = ans2;
				}
			}
		}

		matchCache.set(pos, finalAns);
		return finalAns;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String s = sc.nextLine();
		String p = sc.nextLine();

		char[] ss = s.toCharArray();
		char[] pp = p.toCharArray();
		List<Integer> ans = new ArrayList<Integer>();
		
		ce = new boolean[ss.length + 1][ss.length + 1];
		c = new int[ss.length + 1][ss.length + 1];
		cme = new boolean[ss.length + 1];
		cm = new int[ss.length + 1][];
		
		for (int i = 0; i < ss.length; i++) {
			int sol = solve(ss, pp, 0, i);
			ans.add(sol);
		}
		
		ans.add(0);

		StringBuilder sb = new StringBuilder();
		if (ans.size() > 0) {
			sb.append(ans.get(0).toString());
			for (int i = 1; i < ans.size(); i++) {
				sb.append(' ');
				sb.append(ans.get(i).toString());
			}
		}

		System.out.println(sb.toString());

	}
	
//	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
//
//		String s = sc.nextLine();
//		String p = sc.nextLine();
//
//		char[] ss = s.toCharArray();
//		char[] pp = p.toCharArray();
//
//		if (s.startsWith("aaaabgbabmbabadafbdba")) {
//
//			for (int i = 0; i + pp.length - 1 < ss.length; i++) {
//				boolean isok = true;
//				for (int j = 0; j < pp.length; j++) {
//					if (ss[i + j] != pp[j]) {
//						isok = false;
//						break;
//					}
//				}
//
//				if (isok) {
//					StringBuilder sb = new StringBuilder();
//					for (int j = i; j < Math.min(ss.length, i + 30); j++) {
//						sb.append(ss[j]);
//					}
//					System.out.println(i + " " + sb.toString());
//					i += pp.length;
//				}
//			}
//
//		}
//
//		matchCache = new ArrayList<List<Integer>>();
//		for (int i = 0; i <= ss.length; i++) {
//			matchCache.add(null);
//		}
//
//		List<Integer> matches = bestMatches(ss, pp, 0);
//		List<Integer> ans = new ArrayList<Integer>();
//		if (matches == null) {
//			for (int i = 0; i < ss.length; i++) {
//				ans.add(0);
//			}
//		} else {
//			Collections.sort(matches);
//			int toLetGo = ss.length - matches.size() * pp.length;
//			for (int i = 0; i < ss.length; i++) {
//				int sol = 0;
//				int x = i;
//
//				if (x <= toLetGo) {
//					for (int j = 0; j < matches.size(); j++) {
//						int cur = matches.get(j);
//						int change = Math.min(cur, x);
//						cur -= change;
//						x -= change;
//						if (cur == 0) {
//							sol++;
//						} else {
//							break;
//						}
//					}
//				} else {
//					sol = matches.size();
//					x -= toLetGo;
//
//					int pl = p.length();
//					sol -= x / pl;
//					if (x % pl > 0) {
//						sol--;
//					}
//				}
//
//				ans.add(sol);
//			}
//		}

//		ans.add(0);
//
//		StringBuilder sb = new StringBuilder();
//		if (ans.size() > 0) {
//			sb.append(ans.get(0).toString());
//			for (int i = 1; i < ans.size(); i++) {
//				sb.append(' ');
//				sb.append(ans.get(i).toString());
//			}
//		}
//
//		System.out.println(sb.toString());
//	}
}
