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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class PalindromicCharacteristics3 {
    
    int N = 5010;
    
    int p;
    int[] s = new int[N];
    
    int sz;                      
    int last;                     
    int[] len = new int[N];      
    int[][] nxt = new int[N][26]; 
    int[] suff = new int[N];     
    
    int[] deg = new int[N];  
    int[] cnt = new int[N];  
    int[] half = new int[N];
    
    void solve() {
        char[] ch = in.nextToken().toCharArray();
        int n = ch.length;
        
        init();
        for (int i = 0; i < n; i++) add(ch[i] - 'a');
        
        int[] res = new int[n + 1];
        for (int i = sz; i > 2; i--) {
            res[deg[i]] += cnt[i];
            cnt[suff[i]] += cnt[i];
        }
        for (int i = n - 1; i > 0; i--) res[i] += res[i + 1];
        
        for (int i = 1; i <= n; i++) {
            if (i > 1) out.print(' ');
            out.print(res[i]);
        }
    }
    
    void add(int x) {
        s[++p] = x;
        int cur = find(last);
        if (nxt[cur][x] == 0) {
            ++sz;
            len[sz] = len[cur] + 2;
            nxt[cur][x] = sz;
            if(len[sz] == 1) suff[sz] = 2;
            else suff[sz] = nxt[find(suff[cur])][x];

            int q = nxt[find(half[last])][x];
            while (len[q] > len[sz] / 2) q = suff[q];
            deg[sz] = len[q] > 0 && len[q] == len[sz] / 2 ? deg[q] + 1 : 1;
            half[sz] = q;
        }
        last = nxt[cur][x];
        cnt[last]++;
    }
    
    int find(int t) {
        while (s[p] != s[p - len[t] - 1]) t = suff[t];
        return t;
    }
    
    void init() {
        s[0] = -1;
        sz = 2;
        last = 2;
        len[1] = -1;
        suff[1] = 1;
        half[1] = 1;
        len[2] = 0;
        suff[2] = 1;
        half[2] = 1;
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new PalindromicCharacteristics3().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}