Problem: Palindromic characteristics of string s with length |s| is a sequence of |s| integers, where k-th number is the total number of non-empty substrings of s which are k-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is k-palindrome (k > 1) if and only if: 

  1. Its left half equals to its right half. 
  2. Its left and right halfs are non-empty (k - 1)-palindromes. 



The left half of string t is its prefix of length ⌊|t| / 2⌋, and right half — the suffix of the same length. ⌊|t| / 2⌋ denotes the length of string t divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.

Input

The first line contains the string s (1 ≤ |s| ≤ 5000) consisting of lowercase English letters.

Output

Print |s| integers — palindromic characteristics of string s.

Examples

Input

abba


Output

6 1 0 0 


Input

abacaba


Output

12 4 1 0 0 0 0 

Note

In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
public class Main
{
	
	private void solve()throws IOException
	{
		char s[]=(" "+nextLine()).toCharArray();
		int n=s.length-1;
		int deven[]=new int[n+1];//max even length of palindrome with centre i
		int dodd[]=new int[n+1];//max odd length of palindrome with centre i
		int type[][]=new int[n+1][n+1];//max type of substring i,j
		for(int i=1;i<=n;i++)
		{
			for(int j=1;i-j>=1 && i+j<=n;j++)
			{
				if(s[i-j]==s[i+j])
					dodd[i]++;
				else
					break;
			}
			for(int j=1;i-j+1>=1 && i+j<=n;j++)
			{
				if(s[i-j+1]==s[i+j])
					deven[i]++;
				else
					break;
			}
		}
		long ans[]=new long[n+1];
		for(int l=1;l<=n;l++)
		{
			for(int i=1;i+l-1<=n;i++)
			{
				int j=i+l-1;
				if(l==1)
					type[i][j]=1;
				else
				{
					int t=type[i][i+l/2-1];
					if(l%2==0 && deven[i+l/2-1]>=l/2)
						type[i][j]=t+1;
					else if(l%2==1 && dodd[i+l/2]>=l/2)
						type[i][j]=t+1;
					else
						type[i][j]=0;
				}
				ans[type[i][j]]++;
			}
		}
		for(int i=n-1;i>=1;i--)
			ans[i]=ans[i]+ans[i+1];
		for(int i=1;i<=n;i++)
			out.print(ans[i]+" ");
	}

	 
	///////////////////////////////////////////////////////////

	public void run()throws IOException
	{
		br=new BufferedReader(new InputStreamReader(System.in));
		st=null;
		out=new PrintWriter(System.out);

		solve();

		br.close();
		out.close();
	}
	public static void main(String args[])throws IOException{
		new Main().run();
	}
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	String nextToken()throws IOException{
		while(st==null || !st.hasMoreTokens())
		st=new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	String nextLine()throws IOException{
		return br.readLine();
	}
	int nextInt()throws IOException{
		return Integer.parseInt(nextToken());
	}
	long nextLong()throws IOException{
		return Long.parseLong(nextToken());
	}
	double nextDouble()throws IOException{
		return Double.parseDouble(nextToken());
	}
}