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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
unsigned long long read() {
  unsigned long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
unsigned long long n, f[5005][5005], bas[5005], Hash1[5005], Hash2[5005],
    c[5005];
char ch[5005];
unsigned long long gethash1(unsigned long long l, unsigned long long r) {
  return Hash1[r] - Hash1[l - 1] * bas[r - l + 1];
}
unsigned long long gethash2(unsigned long long l, unsigned long long r) {
  return Hash2[l] - Hash2[r + 1] * bas[r - l + 1];
}
unsigned long long Palindrome(unsigned long long l, unsigned long long r) {
  if (l == r) return 1;
  if ((r - l + 1) % 2) {
    unsigned long long mid = (l + r) >> 1;
    if (gethash1(l, mid - 1) == gethash2(mid + 1, r))
      return 1;
    else
      return 0;
  } else {
    unsigned long long mid = (l + r) >> 1;
    if (gethash1(l, mid) == gethash2(mid + 1, r))
      return 1;
    else
      return 0;
  }
}
signed main() {
  scanf("%s", (ch + 1));
  n = strlen(ch + 1);
  for (unsigned long long i = 1; i <= n; i++) f[i][i] = 1, c[1]++;
  bas[0] = 1;
  for (unsigned long long i = 1; i <= n; i++) bas[i] = bas[i - 1] * 44042137;
  for (unsigned long long i = 1; i <= n; i++)
    Hash1[i] = Hash1[i - 1] * 44042137 + ch[i];
  for (unsigned long long i = n; i >= 1; i--)
    Hash2[i] = Hash2[i + 1] * 44042137 + ch[i];
  for (unsigned long long i = 2; i <= n; i++) {
    for (unsigned long long j = 1; j + i - 1 <= n; j++) {
      unsigned long long ed = j + i - 1;
      if (!Palindrome(j, ed)) continue;
      unsigned long long mid = (j + ed) >> 1;
      if ((ed - j + 1) % 2) {
        unsigned long long mid = (j + ed) >> 1;
        f[j][ed] = f[j][mid - 1] + 1;
      } else {
        unsigned long long mid = (j + ed) >> 1;
        f[j][ed] = f[j][mid] + 1;
      }
      c[f[j][ed]]++;
    }
  }
  for (unsigned long long i = n; i >= 1; i--) c[i] += c[i + 1];
  for (unsigned long long i = 1; i <= n; i++) printf("%d ", c[i]);
  return 0;
}