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;
using ll = long long int;
void init_pwr(vector<ll> &pwr, ll prime, ll mod) {
  pwr.push_back(1);
  for (ll i = 1; i < 5005; i++) {
    pwr.push_back(pwr.back() * prime % mod);
  }
}
vector<ll> hsh(string s, ll mod, vector<ll> &pwr) {
  ll n = s.size(), i, j, k;
  vector<ll> h(n + 1, 0);
  for (i = 0; i < n; i++) {
    ll num = s[i] - 'a' + 2;
    h[i + 1] = (h[i] + num * pwr[i]) % mod;
  }
  return h;
}
ll compute(vector<ll> &h, ll l, ll r, ll mod) {
  return (h[r] - h[l - 1] + mod) % mod;
}
ll dp[5005][5005];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) {
    string s;
    cin >> s;
    ll n = s.size(), i, j, k;
    vector<ll> pwr1, pwr2;
    ll prime1 = 31, prime2 = 89;
    ll mod1 = 1e9 + 7, mod2 = (1LL << 31) - 1;
    init_pwr(pwr1, prime1, mod1);
    init_pwr(pwr2, prime2, mod2);
    vector<ll> h1 = hsh(s, mod1, pwr1);
    vector<ll> h2 = hsh(s, mod2, pwr2);
    for (i = 1; i <= n; i++) dp[i][1] = 1;
    for (i = 1; i + 1 <= n; i++) {
      if (s[i - 1] == s[i]) dp[i][2] = 2;
    }
    for (ll l = 3; l <= n; l++) {
      for (i = 1; i + l - 1 <= n; i++) {
        if (dp[i + 1][l - 2] > 0 && s[i - 1] == s[i + l - 2]) {
          k = l / 2;
          ll h11 = compute(h1, i, i + k - 1, mod1);
          ll h12 = compute(h1, i + l - k, i + l - 1, mod1);
          h11 = h11 * pwr1[i + l - k - 1] % mod1;
          h12 = h12 * pwr1[i - 1] % mod1;
          ll h21 = compute(h2, i, i + k - 1, mod2);
          ll h22 = compute(h2, i + l - k, i + l - 1, mod2);
          h21 = h21 * pwr2[i + l - k - 1] % mod2;
          h22 = h22 * pwr2[i - 1] % mod2;
          if (h11 == h12 && h21 == h22)
            dp[i][l] = dp[i][k] + 1;
          else
            dp[i][l] = 1;
        }
      }
    }
    vector<ll> ans(n + 1, 0);
    for (j = 1; j <= n; j++) {
      for (i = 1; i + j - 1 <= n; i++) {
        if (dp[i][j]) {
          ans[dp[i][j]]++;
        }
      }
    }
    for (i = n - 1; i >= 1; i--) ans[i] += ans[i + 1];
    for (i = 1; i <= n; i++) cout << ans[i] << " ";
  }
  return 0;
}