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;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
inline void normal(long long int &a) {
  a %= 1000000007;
  (a < 0) && (a += 1000000007);
}
inline long long int modMul(long long int a, long long int b) {
  a %= 1000000007, b %= 1000000007;
  normal(a), normal(b);
  return (a * b) % 1000000007;
}
inline long long int modAdd(long long int a, long long int b) {
  a %= 1000000007, b %= 1000000007;
  normal(a), normal(b);
  return (a + b) % 1000000007;
}
inline long long int modSub(long long int a, long long int b) {
  a %= 1000000007, b %= 1000000007;
  normal(a), normal(b);
  a -= b;
  normal(a);
  return a;
}
inline long long int modPow(long long int b, long long int p) {
  long long int r = 1;
  while (p) {
    if (p & 1) r = modMul(r, b);
    b = modMul(b, b);
    p >>= 1;
  }
  return r;
}
inline long long int modInverse(long long int a) {
  return modPow(a, 1000000007 - 2);
}
inline long long int modDiv(long long int a, long long int b) {
  return modMul(a, modInverse(b));
}
inline bool isInside(pair<int, int> p, long long int n, long long int m) {
  return (p.first >= 0 && p.first < n && p.second >= 0 && p.second < m);
}
inline bool isInside(pair<int, int> p, long long int n) {
  return (p.first >= 0 && p.first < n && p.second >= 0 && p.second < n);
}
inline bool isSquare(long long int x) {
  long long int s = sqrt(x);
  return (s * s == x);
}
inline bool isFib(long long int x) {
  return isSquare(5 * x * x + 4) || isSquare(5 * x * x - 4);
}
inline bool isPowerOfTwo(long long int x) {
  return ((1LL << (long long int)log2(x)) == x);
}
template <typename first, typename second>
ostream &operator<<(ostream &os, const pair<first, second> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}
template <typename first, typename second>
ostream &operator<<(ostream &os, const map<first, second> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << it->first << " = " << it->second;
  }
  return os << "]";
}
clock_t tStart = clock();
void faltu() { cerr << endl; }
template <typename T>
void faltu(T a[], int n) {
  for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
  cerr << endl;
}
template <typename T, typename... hello>
void faltu(T arg, const hello &...rest) {
  cerr << arg << ' ';
  faltu(rest...);
}
struct func {
  bool operator()(pair<int, int> const &a, pair<int, int> const &b) {
    if (a.first == b.first) return (a.second < b.second);
    return (a.first < b.first);
  }
};
const long long int INF = 0x3f3f3f3f3f3f3f3f;
const long double EPS = 1e-9;
const int inf = 0x3f3f3f3f;
const int mx = (int)5000 + 9;
long long int n, m, a, b, t, i, j, d, cs = 0, counT = 0, k, ans = 0, l = 0,
                                      sum1 = 0, sum = 0, Max, Min, num;
string s;
int dp[mx][mx], cnt[mx];
int solve(int l, int r) {
  if (l > r) return 0;
  if (l == r) return 1;
  if (l + 1 == r) {
    if (s[l] == s[r])
      return 2;
    else
      return 0;
  }
  if (dp[l][r] != -1) return dp[l][r];
  if (s[l] != s[r] or solve(l + 1, r - 1) == 0)
    dp[l][r] = 0;
  else
    dp[l][r] = solve(l, l + (r - l + 1) / 2 - 1) + 1;
  return dp[l][r];
}
int main() {
  ios_base::sync_with_stdio(false);
  ;
  memset(dp, -1, sizeof(dp));
  cin >> s;
  s = '#' + s;
  for (int i = 1; i <= (s.size() - 1); i++) {
    for (j = i; j < s.size(); j++) {
      d = solve(i, j);
      cnt[d]++;
    }
  }
  for (i = 5000; i >= 0; i--) cnt[i] = cnt[i] + cnt[i + 1];
  for (i = 1; i < s.size(); i++) cout << cnt[i] << ' ';
  cout << '\n';
}