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

    public class Main {

        public static void main(String[] args) throws IOException {

            boolean local = false;
            if (args.length > 0 && args[0].equals("LOCAL"))
                local = true;

            new Main(local).go();
        }

        boolean LOCAL;
        PrintWriter out;
        Reader in;
        BufferedReader br;

        Main(boolean local) throws IOException {

            this.LOCAL = local;

            try {

                //br = new BufferedReader( new FileReader("input.txt") );
                in = new Reader("input.txt");
                out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
            }
            catch (Exception e) {

                //br = new BufferedReader( new InputStreamReader( System.in ) );
                in = new Reader();
                out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );
            }
        }

        void go() throws IOException {

            int t = 1;

            if (this.LOCAL)
                t = in.nextInt();

            while (t > 0) {

                solve();
                t--;

                if (LOCAL)
                    out.println();

            }

            out.flush();
            out.close();
        }


        int inf = 2000000000;
        int mod = 1000000007;
        double eps = 1e-9;

        int n;
        int m;

        //ArrayList<Integer>[] g = new ArrayList[200010];

        void solve() throws IOException {

            char[] s = in.nextLine().toCharArray();

            int n = s.length;

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

            Arrays.fill(dp[1], 1);
            Arrays.fill(dp[0], 1);

            for (int i = 2; i <= n; i++) {

                for (int j = 1; j < n; j++) {

                    if (i%2 == 0) {

                        if (j-1+i-1 < n && s[j-1] == s[j-1+i-1] && dp[i-2][j] > 0) {

                            dp[i][j-1] = 1;
                            if (dp[i/2][j-1] == dp[i/2][j-1+i/2]) {
                                dp[i][j-1] = dp[i/2][j-1] + 1;
                            }
                        }

                    }
                    else {

                        if (j-1+i-1 < n && s[j-1] == s[j-1+i-1] && dp[i-2][j] > 0) {

                            dp[i][j-1] = 1;
                            if (dp[i/2][j-1] == dp[i/2][j+i/2]) {
                                dp[i][j-1] = dp[i/2][j-1] + 1;
                            }
                        }
                    }
                }
            }

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

            for (int i = 1; i <= n; i++)
                for (int j = 0; j < n; j++)
                    ans[dp[i][j]]++;

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

            for (int i = 0; i < n; i++)
                out.print(ans[i+1] + " ");

        }



        class Edge implements Comparable<Edge> {

            int a;
            int b;
            int c;
            int i;

            Edge(int a, int b, int c, int i) {

                this.a = a;
                this.b = b;
                this.c = c;
                this.i = i;
            }

            public int compareTo(Edge p) {

                if (c > p.c) return 1;
                if (c < p.c) return -1;
                if (i > p.i) return 1;
                if (i < p.i) return -1;
                return 0;
            }
        }

        class Pair implements Comparable<Pair>{

            int a;
            int b;

            Pair(int a, int b) {

                this.a = a;
                this.b = b;
            }

            public int compareTo(Pair p) {

    //            if (a > p.a) return 1;
    //            if (a < p.a) return -1;
                if (b > p.b) return 1;
                if (b < p.b) return -1;
                return 0;
            }
        }

        class Item {

            int a;
            int b;
            int c;

            Item(int a, int b, int c) {
                this.a = a;
                this.b = b;
                this.c = c;
            }

        }

        class Reader {

            BufferedReader  br;
            StringTokenizer tok;

            Reader(String file) throws IOException {
                br = new BufferedReader( new FileReader(file) );
            }

            Reader() throws IOException {
                br = new BufferedReader( new InputStreamReader(System.in) );
            }

            String next() throws IOException {

                while (tok == null || !tok.hasMoreElements())
                    tok = new StringTokenizer(br.readLine());
                return tok.nextToken();
            }

            int nextInt() throws NumberFormatException, IOException {
                return Integer.valueOf(next());
            }

            long nextLong() throws NumberFormatException, IOException {
                return Long.valueOf(next());
            }

            double nextDouble() throws NumberFormatException, IOException {
                return Double.valueOf(next());
            }


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

        }

    }