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:

/**
 * @author: Mehul Raheja
 */
import java.util.*;
import java.io.*;

public class PalinChar2 {

    /*
        Runtime = O()
     */
    static int N, M, K;
    static String s;
    static StringTokenizer st;
    static int[] d;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        int N = s.length();
        int[][] dp = new int[s.length()][s.length() + 1];
        int[] ans = new int[s.length()+1];
        for (int i = 0; i < s.length(); i++) {
            dp[i][0] = 1;
            dp[i][1] = 1;
            
        }
        ans[1] += N;
        
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j+i-1 < N; j++) {
                if(s.charAt(j) != s.charAt(j+i-1) || (i > 2 && dp[j+1][i-2] == 0)){
                     dp[j][i] = 0;
                }else{
                    int deg = 1;
                    int len = i/2;
                    
                    while(dp[j][len] > 0){
                        deg++;
                        len /= 2;
                        if(len == 0){
                            break;
                        }
                    }
                    dp[j][i] = deg;
                    ans[deg]++;
                    //System.out.println(s.substring(j, j+i) + " " + deg);
                    
                }
               
            }
        }
   //     System.out.println(Arrays.toString(ans));
        for (int i = N-1; i >= 0; i--) {
            ans[i] = ans[i] + ans[i+1];
        }
      //  System.out.println(Arrays.toString(ans));
        for (int i = 1; i < N; i++) {
            System.out.print(ans[i] + " ");
        }
        System.out.println(ans[N]);
      //  System.out.println(A);
    }
}