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.*;
public class DreamoonAndStrings
{
	public static final int INFINITY = 1000000000;
	
	public static int n;
	public static int[] cost;
	public static int[] next;
	public static int[][] memo;
	
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		
		String s = in.next();
		String p = in.next();
		
		n = s.length();
		
		cost = new int[s.length()];
		next = new int[s.length()];
		Arrays.fill(next, s.length());
		for(int x = 0; x < s.length(); x++)
		{
			int index = x;
			for(int y = 0; y < p.length(); y++)
			{
				while(index < s.length() && s.charAt(index) != p.charAt(y))
				{
					index++;
					cost[x]++;
				}
				
				if(index == s.length())
				{
					cost[x] = INFINITY;
					break;
				}
				
				index++;
			}
			
			next[x] = index;
		}
		
		memo = new int[s.length()][s.length() + 1];
		for(int z = 0; z < memo.length; z++)
		{
			Arrays.fill(memo[z], -1);
		}
		
		for(int a = 0; a <= s.length(); a++)
		{
			if(a > 0)
			{
				System.out.print(" ");
			}
			
			System.out.print(strings(0, a));
		}
		
		System.out.println();
	}
	
	public static int strings(int index, int x)
	{
		if(index == n)
		{
			if(x == 0)
			{
				return 0;
			}
			else
			{
				return -INFINITY;
			}
		}
		else if(memo[index][x] != -1)
		{
			return memo[index][x];
		}
		else
		{
			int best = strings(index + 1, x);
			
			if(x > 0)
			{
				best = Math.max(best, strings(index + 1, x - 1));
			}
			
			if(x >= cost[index])
			{
				best = Math.max(best, 1 + strings(next[index], x - cost[index]));
			}
			
			return memo[index][x] = best;
		}
	}
}
