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;
long long readi() {
  long long input = 0;
  char c = ' ';
  while (c < '-') {
    c = getchar();
  }
  bool negative = false;
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  while (c >= '0') {
    input = 10 * input + (c - '0');
    c = getchar();
  }
  if (negative) {
    input = -input;
  }
  return input;
}
string reads() {
  string input = "";
  char c = ' ';
  while (c <= ' ') {
    c = getchar();
  }
  while (c > ' ') {
    input += c;
    c = getchar();
  }
  return input;
}
void printi(long long output) {
  if (output == 0) {
    putchar('0');
    return;
  }
  if (output < 0) {
    putchar('-');
    output = -output;
  }
  vector<char> vout;
  while (output) {
    vout.push_back((output % 10) + '0');
    output /= 10;
  }
  for (int i = vout.size() - 1; i >= 0; i--) {
    putchar(vout[i]);
  }
  return;
}
void prints(string output) {
  for (int i = 0; i < output.length(); i++) {
    putchar(output[i]);
  }
  return;
}
int N;
string s;
int arr[5010];
int ans[5010];
long long forw[5010], backw[5010];
long long pw[5010];
int best[5010][5010];
long long ADD(long long a, long long b) { return (a + b) % 1000000861; }
long long SUBT(long long a, long long b) {
  return (a - (b % 1000000861) + 1000000861) % 1000000861;
}
long long MULT(long long a, long long b) { return (a * b) % 1000000861; }
long long getpow(long long a, long long e) {
  if (e == 0) {
    return 1ll;
  }
  long long sqr = getpow(a, e / 2);
  if (e % 2) {
    return MULT(a, MULT(sqr, sqr));
  }
  return MULT(sqr, sqr);
}
long long inv(long long x) { return getpow(x, 1000000861 - 2); }
long long getforw(long long L, long long R) {
  return SUBT(forw[R], MULT(forw[L - 1], pw[R - L + 1]));
}
long long getbackw(long long L, long long R) {
  return SUBT(backw[L], MULT(backw[R + 1], pw[R - L + 1]));
}
bool palin(int L, int R) {
  int mid = (L + R) / 2;
  if ((R - L) % 2) {
    return (getforw(L, mid) == getbackw(mid + 1, R));
  }
  return (getforw(L, mid - 1) == getbackw(mid + 1, R));
}
int solve(int L, int R) {
  if (L > R) {
    return 0;
  }
  if (best[L][R] != -1) {
    return best[L][R];
  }
  if (!palin(L, R)) {
    best[L][R] = 0;
    return 0;
  }
  int mid = (L + R) / 2;
  if ((R - L) % 2) {
    best[L][R] = 1 + solve(L, mid);
  } else {
    best[L][R] = 1 + solve(L, mid - 1);
  }
  return best[L][R];
}
int32_t main() {
  cout << fixed << setprecision(10);
  ios_base::sync_with_stdio(false);
  if (fopen("cf835d.in", "r")) {
    freopen("cf835d.in", "r", stdin);
    freopen("cf835d.out", "w", stdout);
  }
  cin >> s;
  N = s.length();
  for (int i = 0; i < N; i++) {
    arr[i + 1] = s[i];
  }
  pw[0] = 1;
  for (int i = 1; i <= N; i++) {
    pw[i] = MULT(pw[i - 1], 1000861);
  }
  for (int i = 1; i <= N; i++) {
    forw[i] = ADD(MULT(forw[i - 1], 1000861), arr[i]);
  }
  for (int i = N; i >= 1; i--) {
    backw[i] = ADD(MULT(backw[i + 1], 1000861), arr[i]);
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      best[i][j] = -1;
    }
  }
  for (int i = 1; i <= N; i++) {
    for (int j = i; j <= N; j++) {
      ans[solve(i, j)]++;
    }
  }
  for (int i = N; i >= 1; i--) {
    ans[i] += ans[i + 1];
  }
  for (int i = 1; i <= N; i++) {
    cout << ans[i] << ' ';
  }
  cout << '\n';
  return 0;
}