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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using std::abs;
using std::cerr;
using std::cin;
using std::cout;
using std::map;
using std::max;
using std::min;
using std::pair;
using std::set;
using std::string;
using std::swap;
using std::vector;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
void err(vector<string>::iterator it, T a) {
  cerr << it->substr((*it)[0] == ' ') << " = " << a << '\n';
}
template <typename T, typename... Ts>
void err(vector<string>::iterator it, T a, Ts... as) {
  cerr << it->substr((*it)[0] == ' ') << " = " << a << ", ";
  err(++it, as...);
}
struct init {
  init() {
    cin.tie(0);
    std::iostream::sync_with_stdio(0);
    cout << std::fixed << std::setprecision(10);
    cerr << std::fixed << std::setprecision(10);
    srand(time(0));
  }
  ~init() {}
} init;
const int MAXN = 5005, MAXMOD = 3;
const ll MOD[MAXMOD] = {1000000007, 1000000009, 1000000021};
const ll BASE[MAXMOD] = {29, 31, 37};
ll pw[MAXMOD][MAXN];
struct hash_init {
  hash_init() {
    for (int j = 0; j < MAXMOD; ++j) {
      pw[j][0] = 1;
      for (int i = 1; i < MAXN; ++i)
        pw[j][i] = (pw[j][i - 1] * BASE[j]) % MOD[j];
    }
  }
} hash_init;
struct hash_string {
  string s;
  vector<ll> hash[MAXMOD];
  ll get(int num, int l, int r) {
    return (hash[num][r] - hash[num][l - 1] + MOD[num]) % MOD[num];
  }
  bool equal(int l1, int r1, int l2, int r2) {
    if (l1 > l2) {
      swap(l1, l2);
      swap(r1, r2);
    }
    for (int i = 0; i < MAXMOD; ++i)
      if (get(i, l2, r2) != (get(i, l1, r1) * pw[i][l2 - l1]) % MOD[i])
        return false;
    return true;
  }
  void build() {
    s = "#" + s;
    for (int j = 0; j < MAXMOD; ++j) {
      hash[j].assign(s.size(), 0);
      for (uint i = 1; i < s.size(); ++i)
        hash[j][i] = (hash[j][i - 1] + pw[j][i] * (s[i] - 'a' + 1)) % MOD[j];
    }
  }
  hash_string() {}
  hash_string(const string& _s) : s(_s) { build(); }
};
std::istream& operator>>(std::istream& is, hash_string& s) {
  auto& t = (is >> s.s);
  s.build();
  return t;
}
int ans[MAXN][MAXN];
bool isp[MAXN][MAXN];
int sum[MAXN];
int main() {
  hash_string s;
  cin >> s;
  int n = s.s.size() - 1;
  for (int c = 1; c <= n; ++c) {
    for (int l = c, r = c + 0; l >= 1 && r <= n; --l, ++r) {
      if (s.s[l] != s.s[r]) break;
      isp[l][r] = 1;
    }
    for (int l = c, r = c + 1; l >= 1 && r <= n; --l, ++r) {
      if (s.s[l] != s.s[r]) break;
      isp[l][r] = 1;
    }
  }
  for (int l = 1; l <= n; ++l) {
    ans[l][l] = 1;
    for (int r = l + 1; r <= n; ++r) {
      int sz = (r - l + 1) / 2;
      int tl = l + sz - 1;
      int tr = r - sz + 1;
      if (isp[l][tl] && s.equal(l, tl, tr, r))
        ans[l][r] = ans[l][tl] + 1;
      else if (isp[l][r])
        ans[l][r] = 1;
      ;
    }
  }
  for (int l = 1; l <= n; ++l)
    for (int r = l; r <= n; ++r) sum[ans[l][r]]++;
  int aft = 0;
  for (int i = n; i >= 1; --i) {
    int bef = aft;
    bef += sum[i];
    sum[i] += aft;
    aft = bef;
  }
  for (int i = 1; i <= n; ++i) cout << sum[i] << ' ';
  cout << '\n';
  return 0;
}