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;
const long long N = 5000 + 10, NM = 1 << 16, MOD = 1e9 + 7, INF = 1e15 + 10,
                SQ = 640, LOG = 20, BH = 723, BH2 = 87651, MH = 1610612741,
                MH2 = 924467661;
long long n, m, x1, x2, z, x, y, y2, t, maxi, ans, mini, ptr, k, p, pos, posi,
    l, r, pw[2][N], hshl[2][N], hshr[2][N], dp[N][N], cnt[N];
string s;
pair<long long, long long> hsh(long long l, long long r, long long q,
                               long long mod) {
  long long tmp1 = hshl[q][r];
  if (l) {
    tmp1 -= (hshl[q][l - 1] * pw[q][r - l + 1]) % mod;
    tmp1 += mod;
    tmp1 %= mod;
  }
  long long tmp2 = hshr[q][l];
  if (r != n - 1) {
    tmp2 -= (hshr[q][r + 1] * pw[q][r - l + 1]) % mod;
    tmp2 += mod;
    tmp2 %= mod;
  }
  return {tmp1, tmp2};
}
long long hsh2(long long l, long long r, long long q, long long mod) {
  long long tmp1 = hshl[q][r];
  if (l) {
    tmp1 -= (hshl[q][l - 1] * pw[q][r - l + 1]) % mod;
    tmp1 += mod;
    tmp1 %= mod;
  }
  return tmp1;
}
bool pali(long long l, long long r) {
  return (hsh(l, r, 0, MH).first == hsh(l, r, 0, MH).second &&
          hsh(l, r, 1, MH2).first == hsh(l, r, 1, MH2).second);
}
bool brabr(long long x, long long y, long long l, long long r) {
  return (hsh2(x, y, 0, MH) == hsh2(l, r, 0, MH) &&
          hsh2(x, y, 1, MH2) == hsh2(l, r, 1, MH2));
}
void prehash(long long base, long long mod, long long q) {
  pw[q][0] = 1;
  for (int i = 1; i < N; i++) {
    pw[q][i] = pw[q][i - 1] * base;
    pw[q][i] %= mod;
  }
  for (int i = 0; i < n; i++) {
    if (i) {
      hshl[q][i] = hshl[q][i - 1] * base;
      hshl[q][i] %= mod;
    }
    hshl[q][i] += s[i];
    hshl[q][i] %= mod;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (i != n - 1) {
      hshr[q][i] = hshr[q][i + 1] * base;
      hshr[q][i] %= mod;
    }
    hshr[q][i] += s[i];
    hshr[q][i] %= mod;
  }
}
int main() {
  cin >> s;
  n = s.size();
  prehash(BH, MH, 0);
  prehash(BH2, MH2, 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j + i - 1 < n; j++) {
      int k = i + j - 1;
      int mid = i / 2;
      int mid1 = j + mid - 1, mid2 = k - mid + 1;
      if (pali(j, k)) dp[j][k] = 1;
      if (i > 1 && brabr(j, mid1, mid2, k)) {
        dp[j][k] += dp[j][mid1];
      }
      cnt[dp[j][k]]++;
    }
  }
  for (int i = N - 2; i >= 0; i--) cnt[i] += cnt[i + 1];
  for (int i = 1; i <= n; i++) cout << cnt[i] << ' ';
}