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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class D427 {
    static final long mod = 1_000_000_009;
    static final long p = 31;
    public static void main(String[] args) {
        FS scan = new FS(System.in);
        String s = scan.next();
        String srev = new StringBuilder(s).reverse().toString();
        int N = s.length();
        
        boolean[][] pal = new boolean[N][N];
        for(int i=0;i<N;i++){
            pal[i][i] = true;
            for(int j=1;j<N;j++){
                if(i-j<0||i+j>=N)break;
                pal[i-j][i+j] = s.charAt(i-j)==s.charAt(i+j) && pal[i-j+1][i+j-1];
                if(!pal[i-j][i+j])break;
            }
            if(i<N-1 && s.charAt(i)==s.charAt(i+1)){
                pal[i][i+1] = true;
                for(int j=1;j<N;j++){
                    if(i-j<0||i+j+1>=N)break;
                    pal[i-j][i+j+1] = s.charAt(i-j)==s.charAt(i+j+1) && pal[i-j+1][i+j];
                    if(!pal[i-j][i+j+1])break;
                }
            }
        }
        
        short[][] memo = new short[N][N];
        int[] count = new int[N+1];
        count[1] = N;
        for(int i=0;i<N;i++)memo[i][i] = 1;
        for(int i=2;i<=N;i++){
            for(int j=0;j<=N-i;j++){
                int start = j+i - (i>>1);
                
                if(pal[j][j+i-1]){
                    short a = memo[j][j+i/2 - 1], b = memo[start][start + i/2 - 1];
                    count[memo[j][j+i-1] = (short) (Math.min(a, b)+1)]++;
                }
            }
        }
        
        
        PrintWriter out = new PrintWriter(System.out);
        int sum = 0;
        for(int i=N;i>=1;i--)
            sum = count[i]+=sum;
        for(int i=1;i<=N;i++){
            out.print(count[i]+" ");
        }
        out.close();
        
    }
    private static class FS {
        BufferedReader br;
        StringTokenizer st;
        public FS(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String next(){
            while(st==null||!st.hasMoreElements()){
                try{st = new StringTokenizer(br.readLine());}
                catch(IOException e){e.printStackTrace();}
            }
            return st.nextToken();
        }
        int nextInt() {return Integer.parseInt(next());}
        long nextLong() {return Long.parseLong(next());}
        double nextDouble() { return Double.parseDouble(next());}
    }
}