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.util.*;
import java.io.*;
public class Palindromiccharacteristics  {
    
    
    
    /************************ SOLUTION STARTS HERE ************************/
    static final long p = 100151;
    static final int MAX = (int) 5e3 + 10;
    static final long pow[] = new long[MAX + 1];
    // implicit mod (2^63)
    static {
        pow[0] = 1;
        for(int i = 1; i <= MAX; i++) 
            pow[i] = pow[i - 1] * p;
    }
    
    static long hash[];
    
    static long subHash(int l , int r) {
        l++;
        r++;
        return hash[r] - hash[l - 1] * pow[r - l + 1];
    }
    

    private static void solve() {
        
        char str[] = nextLine().toCharArray();
//         long st = System.nanoTime();
        int n = str.length;
        int log = 32 - Integer.numberOfLeadingZeros(n);
        
        boolean DP[][] = new boolean[n][n];
        boolean isPalin[][] = new boolean[n][n];
        
        for(int i = 0; i < n; i++)
            isPalin[i][i] = true;
        for(int i = 0; i < n - 1; i++)
            isPalin[i][i + 1] = str[i] == str[i + 1];
        for(int len = 3; len <= n; len++)
            for(int i = 0; i + len - 1 < n; i++)
                isPalin[i][i + len - 1] = isPalin[i + 1][i + len -2] && str[i] == str[i + len - 1];
        
        hash = new long[n + 1];
        hash[1] = str[0];
        for(int i = 2; i <= n; i++) 
            hash[i] = hash[i - 1] * p + str[i - 1];
        
        int cnt[] = new int[n];
        for(int len = 1; len <= n; len++)
            for(int i = 0; i + len - 1 < n; i++) {
                cnt[0] += isPalin[i][i + len - 1] ? 1 : 0;
                DP[i][i + len - 1] = isPalin[i][i + len - 1];
            }
        
        for(int k = 1; k < log; k++) {
            boolean t[][] = new boolean[n][n];
            for(int len = 2; len <= n; len++)
                for(int i = 0; i + len - 1 < n; i++) {
                    int L = i;
                    int R = i + len - 1;
                    long lH = subHash(L, L + (len / 2) - 1 );
                    long rH = subHash(R - (len / 2) + 1, R );
                    if(lH == rH && DP[L][L + (len / 2) - 1] && DP[R - (len / 2) + 1][R]) {
                        t[L][R] = true;
                        cnt[k]++;
                    }
                }
                    
            DP = t;
        }
        
        for(int a : cnt)
            print(a + " ");

//        println("\nTime : " + (System.nanoTime() - st) / 1e9);
         

    }
    private static void solve2() {
        
        char str[] = nextLine().toCharArray();
        int n = str.length;
        
        boolean isPalin[][] = new boolean[n][n];
        
        for(int i = 0; i < n; i++)
            isPalin[i][i] = true;
        for(int i = 0; i < n - 1; i++)
            isPalin[i][i + 1] = str[i] == str[i + 1];
        for(int len = 3; len <= n; len++)
            for(int i = 0; i + len - 1 < n; i++)
                isPalin[i][i + len - 1] = isPalin[i + 1][i + len -2] && str[i] == str[i + len - 1];
        
        hash = new long[n + 1];
        hash[1] = str[0];
        for(int i = 2; i <= n; i++) 
            hash[i] = hash[i - 1] * p + str[i - 1];
        
        int DP[][] = new int[n][n];
        int cnt[] = new int[n];
        cnt[0] += n;
        for(int i = 0; i < n; i++)
            DP[i][i] = 1;

        for(int len = 2; len <= n; len++)
            for(int i = 0; i + len - 1 < n; i++) {
                int L = i;
                int R = i + len - 1;
                long lH = subHash(L, L + (len / 2) - 1 );
                long rH = subHash(R - (len / 2) + 1, R );
                if(lH == rH && isPalin[L][L + (len / 2) - 1]) { // All k palindromes are k-1 , k-2 ... 1 palindromes
                    DP[L][R] = DP[L][L + (len / 2) - 1] + 1;
                    cnt[DP[L][R] - 1]++;
                } else if(isPalin[L][R]) {                      // Only 1 palindrome
                    DP[L][R] = 1;
                    cnt[DP[L][R] - 1]++;
                }
            }
        
        for(int i = n - 2; i >= 0; i--)
            cnt[i] += cnt[i + 1];
        
        for(int a : cnt)
            print(a + " ");
    }
    
    
    /************************ SOLUTION ENDS HERE ************************/
    
    
    
    
    
    /************************ TEMPLATE STARTS HERE **********************/
    
    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
        st     = null;
        solve2();
        reader.close();
        writer.close();
    }
    static BufferedReader reader;
    static PrintWriter    writer;
    static StringTokenizer st;
    
    static String next()
    {while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}            
    st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
    static String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}             
    static int    nextInt()   {return Integer.parseInt(next());}
    static long   nextLong()  {return Long.parseLong(next());}     
    static double nextDouble(){return Double.parseDouble(next());}
    static char   nextChar()  {return next().charAt(0);}
    static int[]  nextIntArray(int n)         {int[] a= new int[n];   int i=0;while(i<n){a[i++]=nextInt();}  return a;}
    static long[] nextLongArray(int n)        {long[]a= new long[n];  int i=0;while(i<n){a[i++]=nextLong();} return a;}    
    static int[]  nextIntArrayOneBased(int n) {int[] a= new int[n+1]; int i=1;while(i<=n){a[i++]=nextInt();} return a;}            
    static long[] nextLongArrayOneBased(int n){long[]a= new long[n+1];int i=1;while(i<=n){a[i++]=nextLong();}return a;}            
    static void   print(Object o)  { writer.print(o);  }
    static void   println(Object o){ writer.println(o);}
    
    /************************ TEMPLATE ENDS HERE ************************/
    
}