D. Palindromic characteristics

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:

Its left half equals to its right half.
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.

题意：给出一个字符串，在其中找到1..k阶的回文子串并统计它们的数量。如果一个字符串是一个回文串,则它可以是1阶子串（k阶字符串,要求它的左边和右边都是k-1阶子串）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define N 5010
 5 using namespace std;
 6 char s[N];
 7 int dp[N][N],ans[N],n;
 8 int main(){
 9     scanf("%s",s+1);
10     n=strlen(s+1);
11     for(int i=1;i<=n;++i)
12         dp[i][i]=1,ans[1]++;
13 
14     for(int len=2;len<=n;++len)
15         for(int i=1;i+len-1<=n;++i){
16             int j=i+len-1;
17             if(s[i]!=s[j]||i+1<=j-1&&dp[i+1][j-1]==0)
18                 dp[i][j]=0;
19             else
20                 dp[i][j]=dp[i][i+len/2-1]+1;
21             if(dp[i][j])
22                 ans[dp[i][j]]++;
23         }
24     for(int i=n;i>=1;--i)
25         ans[i]+=ans[i+1];
26     for(int i=1;i<=n;++i)
27         printf("%d ",ans[i]);
28     return 0;
29 }