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.math.*;

public class CF835D {
    public static int dp[][], n;
    public static Hashing hash, rev;
    public static void main(String[] args)throws Exception {
        InputReader in = new InputReader(System.in);
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        String s = in.next();
        n = s.length();
        dp = new int[n+1][n+1];

        for(int [] d: dp) Arrays.fill(d, -1);

        hash = new Hashing(s);
        rev = new Hashing(reverseString(s));


        int ans[] = new int[n+1];

        for(int i = 1; i <= n; i++){
            for(int j = i; j <= n; j++){
                dp[i][j] = solve_2(i, j);
                ans[dp[i][j]]++;
            }
        }

        for(int i = n-1; i >= 1; i--){
            ans[i] += ans[i+1];
        }

        for(int i = 1; i <= n; i++){
            pw.print(ans[i]+" ");
        }


        pw.close();
    }

    static int solve(int x, int y){
        if(x >= y) return dp[x][y]=1;
        if(dp[x][y] != -1) return dp[x][y];
        int len = (y-x+1)/2;
        int l = x+len-1, r = y-len+1;
        int max = 0;

        if(hash.getHash(x, l) == rev.getRevHash(r, y)) max = Math.max(max, 1 + Math.min(solve(x, l), solve(r, y)));

        return dp[x][y] = max;
    }

    static int solve_2(int x, int y){
        if(x > y) return 0;
        if(dp[x][y] != -1) return dp[x][y];
        int len = (y-x+1)/2;
        int l = x+len-1, r = y-len+1;
        int max = 0;
        if(hash.getHash(x, y) == rev.getRevHash(x, y)) max = 1; // checking are they
        if(hash.getHash(x, l) == hash.getHash(r, y)){
            int p = solve_2(x, l), q = solve_2(r, y);
            if(p > 0 && q > 0) max = Math.max(max, 1 + Math.min(p, q));
        }
        return dp[x][y] = max;
    }





    static String reverseString(String sq){
        return new StringBuilder(sq).reverse().toString();
    }



    static  long multiplier = 43;
    static  Random rnd = new Random();
    static  long mod1 = 1174166111 ; //BigInteger.valueOf((int) (1e9 + rnd.nextInt((int) 1e9))).nextProbablePrime().intValue();
    static  long mod2 = 1234201099; // BigInteger.valueOf((int) (1e9 + rnd.nextInt((int) 1e9))).nextProbablePrime().intValue();
    static  long invMultiplier1 = BigInteger.valueOf(multiplier).modInverse(BigInteger.valueOf(mod1)).longValue();
    static  long invMultiplier2 = BigInteger.valueOf(multiplier).modInverse(BigInteger.valueOf(mod2)).longValue();



    static class Hashing {

        long[] hash1, hash2;
        long[] inv1, inv2;
        int n;

        Hashing(String s) {
            n = s.length();
            hash1 = new long[n + 1];
            hash2 = new long[n + 1];
            inv1 = new long[n + 1];
            inv2 = new long[n + 1];
            inv1[0] = 1;
            inv2[0] = 1;

            long p1 = 1;
            long p2 = 1;
            for (int i = 0; i < n; i++) {
                hash1[i + 1] = (hash1[i] + s.charAt(i) * p1) % mod1;
                p1 = p1 * multiplier % mod1;
                inv1[i + 1] = inv1[i] * invMultiplier1 % mod1;
                hash2[i + 1] = (hash2[i] + s.charAt(i) * p2) % mod2;
                p2 = p2 * multiplier % mod2;
                inv2[i + 1] = inv2[i] * invMultiplier2 % mod2;
             }
        }

        long getRevHash(int i, int j){
            return getHash(n-j+1, n-i+1);
        }

        long getHash(int i, int j) { // 1-based index
            i--; j--; // making it 0-based index
            return getHash_2(i, j - i+1);
        }

        long getHash_2(int i, int len) { //0-based index
            return (((hash1[i + len] - hash1[i] + mod1) * inv1[i] % mod1) << 32)
                    + (hash2[i + len] - hash2[i] + mod2) * inv2[i] % mod2;
        }
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next()throws Exception {
            while (tokenizer == null || !tokenizer.hasMoreTokens())
                tokenizer = new StringTokenizer(reader.readLine());
            return tokenizer.nextToken();
        }

        public String nextLine()throws Exception {
            String line = null;
            tokenizer = null;
            line =  reader.readLine();
            return line;
        }

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

        public double nextDouble() throws Exception{
            return Double.parseDouble(next());
        }

        public long nextLong()throws Exception {
            return Long.parseLong(next());
        }

    }
}