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", ""}.
/*
 *
 * @author Mukesh Singh
 *
 */

import java.io.*;
import java.util.*;
import java.text.DecimalFormat;
@SuppressWarnings("unchecked")
public class AB {	
	
	//solve test cases
	void solve() throws Exception {
		String s = in.nextToken();
		String p = in.nextToken();
		int n = s.length();
		int m = p.length();
		int[]A = new int[n];
		for(int i = 0 ; i < n; ++i ){
			int plen = 0 ; int j = i ; int k = 0 ;
			while(plen < m && j < n ){
				if(p.charAt(k)==s.charAt(j)){
					++k ; ++j ;++plen ;
				}else ++j ;
			}
			if(plen == m ) A[i] = j-i ; else A[i] = -1 ;
			//System.out.print(A[i]+" "); 
		}
		//System.out.println();
		int[][] dp = new int[n+1][n+1];
		for(int i = 0 ; i < n ; ++i ){
			for(int j = 0 ; j <= i ; ++j ){
				//no delete
				dp[i+1][j] = Math.max(dp[i+1][j],dp[i][j]);
				dp[i+1][j+1] = Math.max(dp[i+1][j+1],dp[i][j]);
				if(A[i] >= 0 )
					dp[i+A[i]][j+A[i]-m] = Math.max(dp[i+A[i]][j+A[i]-m],dp[i][j]+1);
			}
		}
		for(int i = 0; i <= n ; ++i) System.out.print(dp[n][i]+" ");
		System.out.println();
	}
	//@ main function
	public static void main(String[] args) throws Exception {
		new AB();
	}
	
	InputReader in;
	PrintStream out ;
	DecimalFormat df ;
	AB() {
		try {
			File defaultInput = new File("file.in");
			if (defaultInput.exists()) 
				in = new InputReader("file.in");
			else 
				in = new InputReader();
			defaultInput = new File("file.out");
			if (defaultInput.exists()) 
				out = new PrintStream(new FileOutputStream("file.out"));
			else
				out = new PrintStream(System.out);
			df = new DecimalFormat("######0.00");
			solve();
			out.close();
		} 
		catch (Exception e) {
			e.printStackTrace();
			System.exit(261);
		}
	}
	
	class InputReader {
		BufferedReader reader;
		StringTokenizer tokenizer;
		
		InputReader() {
			reader = new BufferedReader(new InputStreamReader(System.in));
		}
		
		InputReader(String fileName) throws FileNotFoundException {
			reader = new BufferedReader(new FileReader(new File(fileName)));
		}
		
		String readLine() throws IOException {
			return reader.readLine();
		}
		
		String nextToken() throws IOException {
			while (tokenizer == null || !tokenizer.hasMoreTokens())
				tokenizer = new StringTokenizer(readLine());
			return tokenizer.nextToken();
		}
		
		boolean hasMoreTokens() throws IOException {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				String s = readLine();
				if (s == null)
					return false;
				tokenizer = new StringTokenizer(s);
			}
			return true;
		}
		
		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}
		
		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}
		
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(nextToken());
		}
	}
}
