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 target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T isSquare(T x) {
  int y = sqrt(x + 0.5);
  return (y * y) == x;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T1, class T2>
T1 chmin(T1& x, const T2& y) {
  if (T1(y) < x) return x = y;
  return x;
}
template <class T1, class T2>
T1 chmax(T1& x, const T2& y) {
  if (T1(y) > x) return x = y;
  return x;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << '{';
  bool was = false;
  for (const T& x : v) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << '}';
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  os << '[';
  bool was = false;
  for (const T& x : v) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << ']';
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  os << '[';
  bool was = false;
  for (const T& x : v) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << ']';
  return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& m) {
  os << '<';
  bool was = false;
  for (const auto& x : m) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << '>';
  return os;
}
const double EPS = 1e-8;
const int INF = (int)2e9;
const long long LINF = (long long)2e18;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)5e3 + 10;
const int M1 = (int)1e9 + 7;
const int M2 = (int)1e9 + 9;
struct Hash {
  int h1, h2;
  Hash() {}
  Hash(long long x) : h1(x % M1), h2(x % M2) {}
  Hash(long long x, long long y) : h1(x % M1), h2(y % M2) {}
  Hash operator+(const Hash& other) const {
    return Hash(h1 + other.h1, h2 + other.h2);
  }
  Hash operator-(const Hash& other) const {
    return Hash(h1 - other.h1 + M1, h2 - other.h2 + M2);
  }
  Hash operator*(int x) const {
    return Hash((long long)h1 * x, (long long)h2 * x);
  }
  Hash operator*(const Hash& other) const {
    return Hash((long long)h1 * other.h1, (long long)h2 * other.h2);
  }
  bool operator==(const Hash& other) const {
    return h1 == other.h1 && h2 == other.h2;
  }
};
string s;
int n, ans[MAXN];
int dp[MAXN][MAXN];
Hash st[MAXN], h[MAXN];
void f(int l, int r, int L, int R) {
  l++, r++, L++, R++;
  if (dp[l][r] != dp[L][R] || !dp[l][r]) {
    return;
  }
  if ((h[r] - h[l - 1]) * st[n - l] == (h[R] - h[L - 1]) * st[n - L]) {
    dp[l][R] = chmax(dp[l][R], dp[l][r] + 1);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> s, n = s.size();
  st[0] = 1;
  for (int i = 1; i < MAXN; i++) st[i] = st[i - 1] * 257;
  for (int i = 1; i <= n; i++) {
    h[i] = h[i - 1] + st[i] * ((int)s[i - 1]);
  }
  for (int i = 0; i < s.size(); i++) {
    int l = i + 1, r = i - 1;
    while (l && r < n - 1) {
      l--, r++;
      if (s[l] == s[r]) {
        dp[l + 1][r + 1] = 1;
      } else
        break;
    }
    l = i + 1, r = i;
    while (l && r < n - 1) {
      l--, r++;
      if (s[l] == s[r]) {
        dp[l + 1][r + 1] = 1;
      } else
        break;
    }
  }
  for (int len = 1; len <= n; len++) {
    for (int i = 0; i < n; i++) {
      if (i + len > n) break;
      int l1 = i, r1 = i + len - 1;
      int l2 = r1 + 1, r2 = l2 + len - 1;
      if (r2 < n) {
        f(l1, r1, l2, r2);
      }
      l2++, r2++;
      if (r2 < n) {
        f(l1, r1, l2, r2);
      } else
        break;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      ans[dp[i][j]]++;
    }
  }
  for (int i = n; i; i--) ans[i] += ans[i + 1];
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
}