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>
inline int getint() {
  int x = 0, p = 1;
  char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const unsigned long long e = 65436534565367ull;
const int N = 5010;
char s[N];
unsigned long long pw[N], h0[N], h1[N];
int n, dp[N][N], res[N];
bool isP(int l, int r) {
  unsigned long long tx, ty;
  if (!l)
    tx = h0[r];
  else
    tx = h0[r] - h0[l - 1] * pw[r - l + 1];
  ty = h1[l] - h1[r + 1] * pw[r - l + 1];
  return tx == ty;
}
int go(int l, int r) {
  if (dp[l][r] >= 0) return dp[l][r];
  if (l == r) return dp[l][r] = 1;
  int x = (r - l + 1) / 2;
  if (!isP(l, r)) return dp[l][r] = 0;
  int y = go(l, l + x - 1), z = go(r - x + 1, r);
  if (z == y) return dp[l][r] = y + 1;
  return dp[l][r] = 1;
}
int main() {
  memset(dp, -1, sizeof(dp));
  scanf("%s", s);
  n = strlen(s);
  pw[0] = 1;
  for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * e;
  h0[0] = s[0];
  for (int i = 1; i < n; i++) h0[i] = h0[i - 1] * e + s[i];
  for (int i = n - 1; i >= 0; i--) h1[i] = h1[i + 1] * e + s[i];
  for (register int(i) = 0; (i) < (n); ++(i))
    for (int j = i; j < n; j++) res[go(i, j)]++;
  for (int i = n - 1; i >= 1; i--) res[i] += res[i + 1];
  for (int i = 1; i <= n; i++) printf("%d ", res[i]);
  return 0;
}