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:
//package leto;

import java.util.*;
import java.io.*;

public class force_427 {
	static int cons = 100;
	static int [][]dp; 
	static boolean [][]visit; 
	static String s;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		s = scan.next();
		int n = s.length();
		dp = new int [n][n];
		visit = new boolean [n][n];
		int []cnt = new int [n+1];
		for(int len =1;len<=n;len++){
			for(int l = 0;l<n-len+1;l++){
				int r = l+len-1;
				dp[l][r] = getDp(l,r);
				cnt[dp[l][r]]++;
			}
		}
		for(int i = n;i>=1;i--){
			cnt[i-1] += cnt[i];
		}
		for(int i = 1;i<=n;i++){
			System.out.print(cnt[i]+" ");
		}
	}
	private static int getDp(int l, int r) {
		//visit[l][r] = true;
		if(l > r){
			return 0;
		}
		if(l == r){
			dp[l][r] = 1;
			return dp[l][r];
		}
		if(l == r-1){
			if(s.charAt(l) == s.charAt(r)){
				dp[l][r] = 2;
			}
			return dp[l][r];
		}
		if((s.charAt(l) != s.charAt(r))||(dp[l+1][r-1] == 0)){
			return 0;
		} else {
			int m = (l+r+1)/2-1;
			dp[l][r] = dp[l][m]+1;
			return dp[l][r];
		}
	}

}