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.math.BigInteger;
import java.util.*;

public class Template implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            String filename = "";
            if (filename.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(filename + ".in"));
                out = new PrintWriter(filename + ".out");
            }
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine(), " :");
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    int[] readIntArray(int size) throws IOException {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = readInt();
        }
        return res;
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    <T> List<T>[] createGraphList(int size) {
        List<T>[] list = new List[size];
        for (int i = 0; i < size; i++) {
            list[i] = new ArrayList<>();
        }
        return list;
    }

    public static void main(String[] args) {
        new Template().run();
        //new Thread(null, new Template(), "", 1l * 200 * 1024 * 1024).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    long memoryTotal, memoryFree;

    void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            memoryTotal = Runtime.getRuntime().freeMemory();
            init();
            solve();
            out.close();
            if (System.getProperty("ONLINE_JUDGE") == null) {
                time();
                memory();
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    int n;
    int prime1, prime2;
    int mod1, mod2;
    int[] pow1, pow2;
    int[] h1, h2, rh1, rh2;

    void init(char[] s) {
        Random rnd = new Random();
        prime1 = BigInteger.valueOf(3000 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        prime2 = BigInteger.valueOf(4000 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        mod1 = BigInteger.valueOf((int) 1e9 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        mod2 = BigInteger.valueOf((int) 1e9 + (int) 1e6 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        n = s.length;
        pow1 = new int[n];
        pow2 = new int[n];
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i < n; i++) {
            pow1[i] = (int) ((long) pow1[i - 1] * prime1 % mod1);
            pow2[i] = (int) ((long) pow2[i - 1] * prime2 % mod2);
        }
        h1 = new int[n];
        h2 = new int[n];
        h1[0] = h2[0] = s[0];
        for (int i = 1; i < n; i++) {
            h1[i] = (int) ((h1[i - 1] + (long) pow1[i] * s[i]) % mod1);
            h2[i] = (int) ((h2[i - 1] + (long) pow2[i] * s[i]) % mod2);
        }
        rh1 = new int[n];
        rh2 = new int[n];
        rh1[n - 1] = rh2[n - 1] = s[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rh1[i] = (int) ((rh1[i + 1] + (long) pow1[n - 1 - i] * s[i]) % mod1);
            rh2[i] = (int) ((rh2[i + 1] + (long) pow2[n - 1 - i] * s[i]) % mod2);
        }
    }

    long getHash(int L, int R) {
        int hash1 = getHash(L, R, h1, pow1, mod1);
        int hash2 = getHash(L, R, h2, pow2, mod2);
        return ((long) hash1 << 32) | hash2;
    }

    long getRevHash(int L, int R) {
        int hash1 = getRevHash(L, R, rh1, pow1, mod1);
        int hash2 = getRevHash(L, R, rh2, pow2, mod2);
        return ((long) hash1 << 32) | hash2;
    }

    int getHash(int L, int R, int[] h, int[] pow, int mod) {
        int hash = h[R];
        if (L > 0)
            hash -= h[L - 1];
        if (hash < 0)
            hash += mod;
        return (int) ((long) hash * pow[n - R - 1] % mod);
    }

    int getRevHash(int L, int R, int[] rh, int[] pow, int mod) {
        int hash = rh[L];
        if (R < n - 1)
            hash -= rh[R + 1];
        if (hash < 0)
            hash += mod;
        return (int) ((long) hash * pow[L] % mod);
    }

    boolean equals(int L1, int R1, int L2, int R2) {
        return getHash(L1, R1, h1, pow1, mod1) == getHash(L2, R2, h1, pow1, mod1)
                && getHash(L1, R1, h2, pow2, mod2) == getHash(L2, R2, h2, pow2, mod2);

//        long hash1 = getHash(L1, R1);
//        long hash2 = getHash(L2, R2);
//        return hash1 == hash2;
    }

    boolean isPalindrome(int L, int R) {
        return getHash(L, R, h1, pow1, mod1) == getRevHash(L, R, rh1, pow1, mod1)
                && getHash(L, R, h2, pow2, mod2) == getRevHash(L, R, rh2, pow2, mod2);
//
//        long hash = getHash(L, R);
//        long revHash = getRevHash(L, R);
//        return hash == revHash;
    }

    boolean equalsToReversed(int L1, int R1, int L2, int R2) {
        long hash1 = getHash(L1, R1);
        long revHash2 = getRevHash(L2, R2);
        return hash1 == revHash2;
    }

    int[][] res;

    int rank(int l, int r) {
        if (res[l][r] != -2) return res[l][r];
        if (!isPalindrome(l, r)) {
            return res[l][r] = 0;
        }
        int len = (r - l + 1);
        if (len == 1) {
            return res[l][r] = 1;
        }
        int half = len / 2;

        int otherR = l + half - 1;
        int otherL = r - half + 1;

        if (isPalindrome(l, otherR) && equals(l, otherR, otherL, r)) {
            return res[l][r] = rank(l, otherR) + 1;
        } else {
            return res[l][r] = isPalindrome(l, r) ? 1 : 0;
        }
    }

    void solve() throws IOException {
//        char[] s = sb.toString().toCharArray();
        char[] s = readString().toCharArray();
        init(s);
        res = new int[s.length][s.length];
        for (int[] rr : res) Arrays.fill(rr, -2);

//        boolean[][] isPalindrome = new boolean[s.length][s.length];
//        for (int l = 0; l < s.length; l++) {
//            for (int r = 0; r < s.length; r++) {
//                isPalindrome[l][r] = isPalindrome(l, r);
//            }
//        }

        int[] count = new int[s.length + 1];
        for (int l = 0; l < s.length; l++) {
            for (int r = l; r < s.length; r++) {
                if (!isPalindrome(l, r)) {
                    res[l][r] = 0;
                } else {
                    if (l == r) {
                        res[l][r] = 1;
                    } else {
                        int half = (r - l + 1) / 2;

                        int otherR = l + half - 1;
                        int otherL = r - half + 1;

                        if (equals(l, otherR, otherL, r)) {
                            res[l][r] = res[l][otherR] + 1;
                        } else {
                            res[l][r] = 1;
                        }
                    }
                }
                count[res[l][r]]++;
            }
        }

//        for (int i = 0; i < s.length; i++) {
//            for (int j = i; j < s.length; j++) {
//                count[rank(i, j)]++;
//            }
//        }

        for (int i = s.length - 1; i >= 0; i--) {
            count[i] += count[i + 1];
        }
        for (int i = 1; i <= s.length; i++) out.print(count[i] + " ");
    }


}