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

public class PalindromicCharacteristics {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    char[] str = in.readLine().toCharArray();
    int N = str.length;
    //[l][s]
    boolean[][] isPalindrome = new boolean[N+1][N];
    for(int l = 1; l <= N; ++l) {
      for(int s = 0; s <= N - l; ++s)
        isPalindrome[l][s] = (l == 1) || ((l == 2 || isPalindrome[l - 2][s + 1]) && str[s] == str[s + l - 1]);
    }
    int[][] palindromeLevel = new int[N+1][N];
    int[] levels = new int[N + 1];
    for(int l = 1; l <= N; ++l) {
      for(int s = 0; s <= N - l; ++s) {
        if(isPalindrome[l][s]) {
          if(l == 1)
            palindromeLevel[l][s] = 1;
          else
            palindromeLevel[l][s] = 1 + Math.min(palindromeLevel[l/2][s], palindromeLevel[l/2][s + (l - 1)/2 + 1]);
        }
        ++levels[palindromeLevel[l][s]];
      }
    }
    int total = 0;
    for(int level = N; level >= 0; --level)
      levels[level] = total += levels[level];
    for(int i = 1; i < N; ++i)
      System.out.print(levels[i] + " ");
    System.out.println(levels[N]);
  }
}