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", ""}.
var s = readline();
var p = readline();

var n = s.length;
var dp = new Array();
for(var i=0; i<=n; i++)
{
    dp[i] = new Array();
}

var a = new Array();
var b = new Array();

//a[i] = t => a[t]-a[i] contains the pattern, meanwhile it should remove b[i] chars
//dp[i][j] = max(dp[i-1][j-1], dp[i][j-1], dp[i-b[j]][a[j]-1]+1);

for(var m=0; m<s.length; m++)
{
    var i = m;
	var j = p.length - 1;
	a[m] = -1;
	b[m] = 0;
	while(i>=0)
	{
	    if(s[i]==p[j])
		{
		    if(j==0)
			{
				a[m] = i;
				break;
			}
		    i--;
			j--;
		}
		else
		{
		    i--;
			b[m]++;
		}
	}
}

for(var i=0; i<=n; i++)
{
    for(var j=0; j<n; j++)
	{
	    if(i>j+1)
		{
		    dp[i][j] = -1;
			continue;
		}
	    dp[i][j] = 0;
		if(i-1>=0&&j-1>=0&&dp[i-1][j-1]>dp[i][j])
		{
		    dp[i][j] = dp[i-1][j-1];
		}
		if(j-1>=0&&dp[i][j-1]>dp[i][j])
		{
		    dp[i][j] = dp[i][j-1];
		}
		if(a[j]!=-1&&i-b[j]>=0)
		{
		    var tt = 0;
		    if(a[j]==0)
			{
			    if(i-b[j]==0)
			    {tt = 1;}
			}
			else
			{
			    tt = 1 + dp[i-b[j]][a[j]-1];
			}
			if(tt>dp[i][j])
			{
			    dp[i][j] = tt;
			}
		}
	}
}
var res = dp[0][n-1];
for(var i=1; i<=n; i++)
{
    res = res + ' ' + dp[i][n-1];
}
print(res);