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

public class C272E {
	class FastSolver {

		public int[] buildZ(char[] T, char[] P) {
			int n = T.length;
			int p = P.length;
			int[] L = new int[T.length];

			for (int i = 0; i < n; i++) {
				int ppos = p - 1;
				{
					int j = i;
					while (j >= 0 && ppos >= 0) {
						if (T[j] == P[ppos]) {
							ppos--;
						}
						j--;
					}
					if (ppos == -1) {
						L[i] = i - j;
					} else {
						L[i] = -1;
					}

				}
			}
			return L;
		}

		public void Solve() {
			char[] T = n().toCharArray();
			int n = T.length;
			char[] P = n().toCharArray();
			int p = P.length;
			int[] L = buildZ(T, P);
			int[][] dp = new int[T.length][T.length + 1];
//
//			for (int i = 0; i < n; i++) {
//				System.out.print(L[i] + " ");
//			}
//			System.out.println("");
			for (int i = 0; i < n; i++) {
				for (int j = 0; j <= i + 1; j++) {
					if (i > 0) {
						dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
					}
//					System.out.print(" step1: " + dp[i][j]);
					if (j > 0 && i > 0) {
						dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i][j]);
					}
//					System.out.print(" step2: " + dp[i][j]);
					if (L[i] >= 0 && j >= L[i] - p) {
						if (i - L[i] == -1) {
							if (j == L[i] - p)
								dp[i][j] = 1;
						} else {
							int del = j - L[i] + p;
							int pos = i - L[i];
							if (del <= pos + 1)
								dp[i][j] = Math.max(dp[pos][del] + 1, dp[i][j]);
						}
					}

//					System.out.println(" dp [" + i + "][" + j + "] = "
//							+ dp[i][j]);

				}
			}
//			System.out.println("");
			for (int i = 0; i <= n; i++) {
				System.out.print(dp[T.length - 1][i] + " ");
			}

		}

		BufferedReader br;
		StringTokenizer st;

		public FastSolver(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String n() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

		String l() {
			String s = null;
			try {
				s = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return s;

		}

		boolean hasMoreTokens() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

		int nb() {
			return Integer.parseInt(n(), 2);
		}

		long nbl() {
			return Long.parseLong(n(), 2);
		}

		int ni() {
			return Integer.parseInt(n());
		}

		double nd() {
			return Double.parseDouble(n());
		}

		long nl() {
			return Long.parseLong(n());
		}
	}

	public void run() {
		FastSolver in = new FastSolver(System.in);
		PrintWriter out = new PrintWriter(System.out);
		in.Solve();
		out.close();
	}

	public static void main(String[] args) {
		new C272E().run();
	}
}