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 javax.print.attribute.standard.MediaPrintableArea;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.io.*;
import java.util.*;
/**
 * Created by Firеfly on 1/1/2017.
 */
public class Task {
    public static void main(String[] args) throws IOException {
        Emaxx emaxx = new Emaxx();
    }
}


class Emaxx {
    FScanner fs;
    PrintWriter pw;
    int n, off, m, k;
    Integer W;
    ArrayList<Integer>[] graph;
    int[][] to;
    double[] comes, zh;
    int[] nums, res;
    LinkedList<Pair> qoue;
    boolean[] flags;
    Emaxx() throws IOException {
        fs = new FScanner(new InputStreamReader(System.in));
        // pw = new PrintWriter(new FileWriter("arithnumbers.out"));
        //  fs = new FScanner(new FileReader("C:\\Users\\Firеfly\\Desktop\\New Text Document.txt"));
        //     fs = new FScanner(new FileReader("input.txt"));;
        //       pw = new PrintWriter("output.txt");
        PrintWriter pw = new PrintWriter(System.out);
        char[] s = fs.nextLine().toCharArray();
        n = s.length;
        int[][] dp = new int[n][n];
        int f = 0;
        for (int i = 0; i<n; i++)
            dp[i][i] = 1;
        for (int i = 0; i<n-1; i++)
            if (s[i] == s[i+1])
                dp[i][i+1] = 2;
        f = 2;
        while (f<n) {
            for (int i = 0; i+f<n; i++) {
                if (s[i] != s[i+f] || dp[i+1][i+f-1] == 0)
                    dp[i][i+f] = 0;
                else
                    dp[i][i+f] = dp[i][(i+i+f)/2- (f%2== 0? 1 : 0)] + 1;
            }
            f++;
        }
        int[] ans = new int[n];
        for (int i = 0; i<n; i++)
            for (int j= 0; j< n ; j++)
                if (dp[i][j]!=0)
                    ans[dp[i][j]-1]++;
        int tt = 0;
        for (int i =0 ; i<n; i++)
            tt+=ans[i];
        for (int i =0 ; i<n; i++)
        {
            pw.print(tt + " ");
            tt-=ans[i];
        }
        pw.close();
    }
    int gcd (int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd (b, a % b);
    }



}


class Triple {
    int x, y, c;
    Triple(int x1, int y1, int c1) {
        x = x1; y = y1; c = c1;
    }


}
class Pair implements Comparable<Pair>{
    int x, y;
    Pair(int x1, int y1) {x = x1; y = y1;}
    Pair(){}
    @Override
    public int compareTo(Pair o) {
        return Integer.compare(x, o.x);
    }
}

class Algs {
    public static int[] Z_f(char[] s) {
        int[] zf = new int[s.length];
        zf[0] = -1;
        int l = 0, r= 0;
        for (int i = 1; i<s.length; i++) {
            if (i>r)
            {
                int g = i;
                while (g < s.length && s[g] == s[g-i])
                    g++;
                if (g == i)
                    continue;
                l = i;
                r = g-1;
                zf[i] = g-i;
            } else {
                if (zf[i-l]<=r-i+1)
                    zf[i] = zf[i-l];
                else {
                    int g = r+1;
                    while (g <s.length && s[g] == s[g-i])
                        g++;
                    if (g == r+1)
                        zf[i] = r-i+1;
                    else {
                        zf[i] = g-i;
                        r = g-1;
                        l = i;
                    }
                }
            }
        }
        return zf;
    }
}



class FScanner {
    BufferedReader br;
    StringTokenizer st;
    FScanner(InputStreamReader isr) {
        br = new BufferedReader(isr);
    }

    FScanner(FileReader fr) {
        br = new BufferedReader(fr);
    }

    String nextToken() throws IOException{
        while (st == null || !st.hasMoreTokens()) {
            String s = br.readLine();
            if (s == null)
                return null;
            st = new StringTokenizer(s);
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextLine() throws IOException {
        return br.readLine();
    }

    char nextChar() throws IOException {
        return (char) br.read();
    }
}