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

/**
 * 835D
 * θ(|s|^2) time
 * θ(|s|^2) space
 *
 * @author artyom
 */
public class _835D implements Runnable {
    private BufferedReader in;
    private StringTokenizer tok;

    private Object solve() throws IOException {
        CharSequence s = nextToken();
        int n = s.length();
        int[][] ps = new int[n][n + 2]; // Palindromes's degree at positions and lengths
        for (int i = 1; i < n; i++) {
            for (int j = 1; i - j >= 0 && i + j < n; j++) {
                if (s.charAt(i - j) == s.charAt(i + j)) {
                    ps[i - j][j * 2 + 1] = 1; // An odd-length palindrome found
                } else {
                    break;
                }
            }
            for (int j = 1; i - j >= 0 && i + j <= n; j++) {
                if (s.charAt(i - j) == s.charAt(i + j - 1)) {
                    ps[i - j][j * 2] = 1; // An even-length palindrome found
                } else {
                    break;
                }
            }
        }
        int k = 32 - Integer.numberOfLeadingZeros(n);
        int[] cnt = new int[k + 1];
        cnt[1] = n;
        for (int i = 0; i < n; i++) {
            ps[i][1] = 1;
            for (int l = 1, m = (n - i) >> 1; l <= m; l++) {
                int l2 = l << 1;
                if (ps[i][l2] > 0) {
                    ps[i][l2] += ps[i][l];
                    cnt[ps[i][l2]] += 1;
                }
                if (ps[i][l2 + 1] > 0) {
                    ps[i][l2 + 1] += ps[i][l];
                    cnt[ps[i][l2 + 1]] += 1;
                }
            }
        }
        for (int i = k - 1; i > 0; i--) {
            cnt[i] += cnt[i + 1];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= k; i++) {
            sb.append(cnt[i]).append(' ');
        }
        for (int i = k; i < n; i++) {
            sb.append(0).append(' ');
        }
        return sb;
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new _835D().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            tok = null;
            System.out.print(solve());
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }
}