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")
using namespace std;
;
long long max(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
long long min(long long a, long long b) {
  if (a > b)
    return b;
  else
    return a;
}
long long gcd(long long a, long long b) { return (b == 0) ? a : gcd(b, a % b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long normalize(long long x, long long mod) {
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
long long dx[4] = {0, 0, 1, -1};
long long dy[4] = {1, -1, 0, 0};
string abc = "abcdefghijklmnopqrstuvwxyz";
const double PI = acosl(-1);
const long long mod = 1000 * 1000 * 1000 + 7;
const long long inf = 1e18 + 5;
inline long long add(long long a, long long b, long long p = mod) {
  long long c = a + b;
  if (c >= p) c -= p;
  return c;
}
inline long long sub(long long a, long long b, long long p = mod) {
  long long c = a - b;
  if (c < 0) c += p;
  return c;
}
inline long long mul(long long a, long long b, long long p = mod) {
  return (a * 1ll * b) % p;
}
long long floor1(long long n, long long k) {
  if (n % k == 0 || n >= 0) return n / k;
  return (n / k) - 1;
}
long long ceil1(long long n, long long k) { return floor1(n + k - 1, k); }
long long powm(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
const long long N = 5000 + 5;
long long n;
string s;
long long gen_base(const long long before, const long long after) {
  auto seed =
      std::chrono::high_resolution_clock::now().time_since_epoch().count();
  std::mt19937 mt_rand(seed);
  long long base =
      std::uniform_int_distribution<long long>(before + 1, after)(mt_rand);
  return base % 2 == 0 ? base - 1 : base;
}
struct StringHash {
  long long base;
  string s;
  long long n;
  vector<long long> pre;
  vector<long long> powb;
  StringHash(string s, long long p = 255) {
    base = p;
    n = s.size();
    pre.resize(n + 1);
    powb.resize(n + 1);
    pre[0] = 0;
    powb[0] = 1;
    for (long long i = 0; i < n; i++) {
      pre[i + 1] = add(mul(pre[i], base, mod), s[i], mod);
      powb[i + 1] = mul(powb[i], base, mod);
    }
  }
  long long hash(long long i, long long len) {
    if (!len) return 0;
    len = min(len, n - i);
    long long j = i + len - 1;
    long long ans;
    ans = sub(pre[j + 1], mul(pre[i], powb[len], mod), mod);
    return ans;
  }
};
long long dp1[N];
long long dp2[N][N];
void solve() {
  cin >> s;
  n = ((long long)s.size());
  string t = s;
  reverse((t).begin(), (t).end());
  long long p = gen_base(256, mod);
  StringHash hash1(s, p), hash2(t, p);
  for (long long i = (0); i < (n); ++i) {
    for (long long j = (i); j < (n); ++j) {
      long long len = j - i + 1;
      long long h1 = hash1.hash(i, len / 2);
      long long h2 = hash2.hash(n - j - 1, len / 2);
      long long c = 0;
      if (h1 == h2) {
        if (len % 2 == 0) {
          c = dp2[i][max(i + len / 2 - 1, 0)];
        } else {
          if ((i + len / 2 - 1) < 0) {
            c = 0;
          } else {
            c = dp2[i][max(i + len / 2 - 1, 0)];
          }
        }
        ++dp1[c + 1];
        dp2[i][j] = c + 1;
      }
    }
  }
  for (long long i = (n - 1); i > (-1); --i) dp1[i] += dp1[i + 1];
  for (long long i = (1); i < (n + 1); ++i) cout << dp1[i] << " ";
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}