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 A {


	
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
		char []s=sc.next().toCharArray();
		int n=s.length;
		int [][]dp=new int [n][n];
		int []cnt=new int [n+1];
		for(int i=0;i<n;i++)
		{
			dp[i][i]=1;
			cnt[1]++;
			if(i+1<n) {
				dp[i][i+1]=s[i]==s[i+1]?2:0;
				cnt[dp[i][i+1]]++;
			}
		}
		
		
		for(int len=3;len<=n;len++)
			for(int i=0;i+len-1<n;i++)
			{
				int j=i+len-1;
				if(s[i]==s[j] && dp[i+1][j-1]>0)
				{
					int x=i+(j-i+1)/2-1;
					dp[i][j]=dp[i][x]+1;
					cnt[dp[i][j]]++;
					
				}
			}
		int []ans=new int [n+1];
		ans[n]=cnt[n];
		for(int i=n-1;i>0;i--)
			ans[i]=ans[i+1]+cnt[i];
		for(int i=1;i<=n;i++)
			out.print(ans[i]+" ");
		
		out.close();

	}

	static class Scanner
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s)
		{
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException
		{
			br = new BufferedReader(new FileReader(new File((s))));
		}

		public String next() throws IOException
		{
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException
		{
			return br.readLine();
		}

		public double nextDouble() throws IOException
		{ return Double.parseDouble(next()); }	
	}
}