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;
int now, ot, mi, last, cnt, le, d[10010], st[10010][15], len[10010], ans[10010],
    trs[10010][26], fa[10010], tot[10010], lev[10010];
char s[10010];
inline int ext(int x) {
  for (now = last; s[le - len[now]] ^ x; now = fa[now])
    ;
  if (trs[now][x]) return last = trs[now][x];
  for (ot = fa[now]; s[le - len[ot]] ^ x; ot = fa[ot])
    ;
  ++d[fa[++cnt] = trs[ot][x]];
  len[trs[now][x] = cnt] = len[now] + 2;
  return last = cnt;
}
inline void topo() {
  int dl[10010], l = 0, r = 0;
  for (int i = 0; i <= cnt; ++i)
    if (!d[i]) dl[++r] = i;
  while (l < r) {
    int v = fa[dl[++l]];
    tot[v] += tot[dl[l]];
    if (!--d[v]) dl[++r] = v;
  }
}
int main() {
  len[last = cnt = 1] = -1;
  fa[1] = fa[0] = 1;
  for (s[le + 1] = getchar(); s[le + 1] != '\n'; s[++le + 1] = getchar()) {
    ext(s[le + 1] -= 'a' - 1);
    ++tot[last];
    if (!lev[last]) {
      st[last][0] = fa[last];
      for (int i = 1; i <= 13; ++i) st[st[last][i - 1]][i - 1];
      if (len[last] == 1)
        lev[last] = 1;
      else {
        for (mi = 13, now = last; mi >= 0;) {
          while (mi >= 0 && len[st[now][mi]] < len[last] >> 1) --mi;
          if (mi >= 0) now = st[now][mi];
        }
        if (len[now] == len[last] >> 1)
          lev[last] = lev[now] + 1;
        else
          lev[last] = 1;
      }
    }
  }
  topo();
  for (int i = 2; i <= cnt; ++i) ans[lev[i]] += tot[i];
  for (int i = le; i; --i) ans[i - 1] += ans[i];
  for (int i = 1; i <= le; ++i) printf("%d ", ans[i]);
  return 0;
}