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.*;
import java.lang.*;




public class spin {
    public static void main(String[] args)
    {
            FastScanner fi=new FastScanner();
            String si=fi.next();
            int i,j,k,l,m,r,n;
            n=si.length();
            char [] s=si.toCharArray();
            int [][]dp=new int[n][n];
            int [] cnt=new int[n+1];

            for(l=0;l<n;l++)
            {
                for (r=l;r<n;r++)
                {
                    if (l==r) {
                        dp[l][r]++;

                    }
                    else if (l==r-1)
                    {
                        if (s[l]==s[r])
                        {
                            m=(int )Math.ceil((l+r)/2.0)-1;
                       //     System.out.println( " l  = " + l + " r = " +r  + " m = " +m);
                            if (m>=0)
                                dp[l][r]=dp[l][m]+1;
                        }

                    }

                    cnt[dp[l][r]]++;


                }
            }





            for (l=n-2;l>=0;l--)
            {

                for (r = l+2; r <n; r++)
                {


                 //   System.out.println( " l  = " + l + " r = " +r  );



                     if (s[l]!=s[r])
                         dp[l][r]=0;

                   // else if((r>=1 && (l<n-1)  && (l<=(r-2))) && dp[l+1][r-1]==0)
                  //   dp[l][r]=0;

                    else if   (  s[l]==s[r] )
                    {
                        m=(int )Math.ceil((l+r)/2.0)-1;
                        //System.out.println( " l  = " + l + " r = " +r  + " m = " +m);
                        if (m>=0 &&(r>=1 && (l<n-1)  && (l<=(r-2))) && dp[l+1][r-1]!=0)
                        dp[l][r]=dp[l][m]+1;

                }
                    cnt[dp[l][r]]++;

                }
            }
       /*     for (l=0;l<n;l++)
            {
                for (r=l;r<n;r++)
                {
                    System.out.print(dp[+l][+r] + " ");
                }
                    System.out.println();
            }

        for (i=1;i<=n;i++)
            System.out.print(cnt[+i] + " ");

        System.out.println();
*/

            int ans[]=new int [n+1];
        int total_sum=0;
        int partial_sum=0;


            for (i=1;i<=n;i++)
            {
                total_sum=total_sum+cnt[i];
            }
            for (i=1;i<=n;i++)
            {
                ans[i]=total_sum;
                partial_sum=cnt[i];
                total_sum=total_sum-partial_sum;
                if (ans[i] <0)
                    ans[i]=0;
                System.out.print(ans[+i] + " ");
            }

















    }


}

class FastScanner

{
    BufferedReader br;
    StringTokenizer st;

    FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

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

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