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.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
	
	// ArrayList<Integer> lis = new ArrayList<Integer>();
	// ArrayList<String> lis = new ArrayList<String>();
	//  PriorityQueue<P> que = new PriorityQueue<P>();
	// PriorityQueue<Integer> que = new PriorityQueue<Integer>();
	//  Stack<Integer> que = new Stack<Integer>();
	//HashMap<Long,Long> map = new HashMap<Long,Long>();
    //	static long sum=0;
	// 1000000007 (10^9+7)
	static int mod = 1000000007;
	//static int mod = 1000000009,r=0; ArrayList<Integer> l[]= new ArrayList[n];
   // static int dx[]={1,-1,0,0};
//	static int dy[]={0,0,1,-1};
//	static int dx[]={1,-1,0,0,1,1,-1,-1};
//  static int dy[]={0,0,1,-1,1,-1,1,-1};
	//static Set<Integer> set = new HashSet<Integer>();

	//static ArrayList<Integer> l[];
    //static int parent[][],depth[],node,max_log;


			  
public  static void main(String[] args)   throws Exception, IOException{
   //String line=""; throws Exception, IOException
   //(line=br.readLine())!=null
	//Scanner sc =new Scanner(System.in);
	
	Reader sc = new Reader(System.in);
   
	
	//int n=sc.nextInt(), m=sc.nextInt(); 
	//int n=sc.nextInt();


	char a[]=sc.nextString().toCharArray();
	char b[]=sc.nextString().toCharArray();

	
	int l=a.length,ll=b.length;
	int d[][]=new int[l+1][l+1], c[]=new int[l+1];
	
	
	for (int i = 0; i < l; i++) {
		
		if( a[i]!=b[0] )c[i]--;
		else{
			int k=0;
		for (int j = i; j < l ; j++) {
			if( a[j]==b[k] ){k++; if( k==ll ){ c[i]=j;break; } }	
		}
		  if(k<ll)c[i]--;
		}
	}

    // db(a,b,c);
 
     
      for (int i = 1; i <= l; i++) {
    	  
    	  d[i][0]=max(d[i-1][0],d[i][0]);
    	 
    	  for (int j = 1; j <= i; j++) {
			d[i][j]=max( d[i][j],d[i-1][j-1] );
			d[i][j]=max( d[i][j],d[i-1][j] );
		}
    	  
    	  if( c[i-1]>=0 ){
    		  int x=c[i-1]+1, rm=x-i+1-ll;
    	 db(i,rm);
    		  for (int j = 0; j <= i-1 ; j++) {
    				d[x][j+rm]=max( d[x][j+rm], d[i-1][j]+1  );
    			}
    		  
    	  }
    	  
    	//  db(i,d[i]);
    	  
	}     
     
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i <= l; i++) {
		sb.append(d[l][i]+" ");
	}
    System.out.println(sb);
    
}


/*
  static class P implements Comparable<P>{
	int id, d; ;
	P(int id,int d){
		this.id=id;
		this.d=d;
	} 
	
	public int compareTo(P x){
	//	return  (-x.d+d)>=0?1:-1  ; // ascend long
		return   -x.d+d  ; // ascend
	//	 return   x.d-d  ; //descend
	   }
 
}
*/



  

static void db(Object... os){
    System.err.println(Arrays.deepToString(os));

}


}




class Reader
{ 
	private BufferedReader x;
	private StringTokenizer st;
	
	public Reader(InputStream in)
	{
		x = new BufferedReader(new InputStreamReader(in));
		st = null;
	}
	public String nextString() throws IOException
	{
		while( st==null || !st.hasMoreTokens() )
			st = new StringTokenizer(x.readLine());
		return st.nextToken();
	}
	public int nextInt() throws IOException
	{
		return Integer.parseInt(nextString());
	}
	public long nextLong() throws IOException
	{
		return Long.parseLong(nextString());
	}
	public double nextDouble() throws IOException
	{
		return Double.parseDouble(nextString());
	}
}