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

    static int MOD1=1000000007;
    static int MOD2=998244353;
    static int B=(int) (Math.random()*900000000)+26;//Anti Hack
    public static void main(String[] args) throws IOException{
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine();
        int len=str.length();
        int[][] pref=new int[len][len];//Prefix hashing
        //long[][] pref2=new long[len][len];//Multiple primes
       
        int[][] dp=new int[len][len];//Max palindrome level
        int[] ans=new int[len+1];
        for (int i = 0; i < len; i++) {
            dp[i][i]=1; pref[i][i]=(str.charAt(i)-97); ans[1]++;
            //pref2[i][i]=(str.charAt(i)-97); 
        }
        for (int d = 1; d < len; d++) {
            for (int i = 0; i < len-d; i++) {
                pref[i][i+d]=(int)((long)(pref[i][i+d-1])*B+(str.charAt(i+d)-97))%MOD1;
                
                //pref2[i][i+d]=((pref[i][i+d-1])*B+(str.charAt(i+d)-97))%MOD2;
                
                if((d==1 && str.charAt(i)==str.charAt(i+1)) || (str.charAt(i)==str.charAt(i+d) && dp[i+1][i+d-1]>0)){
                    dp[i][i+d]=1;
                }
                if(dp[i][i+d]>0 && 
                        pref[i][i+(d-1)/2]==pref[i+d-(d-1)/2][i+d] ){//&& pref2[i][i+(d-1)/2]==pref2[i+d-(d-1)/2][i+d]
                    dp[i][i+d]=dp[i][i+(d-1)/2]+1;
                }
                for (int j = 1; j <=dp[i][i+d]; j++) {
                    ans[j]++;
                }
            }
        }
        StringBuilder sb=new StringBuilder();
        for (int i = 1; i <=len; i++) {
            sb.append(ans[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
    
}