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;
struct Hash {
  vector<long long int> fhash, rhash, powr;
  long long int p = 31, n;
  Hash(string s) {
    n = (long long int)s.size();
    fhash.resize(n + 1, 0);
    powr.resize(n + 1, 0);
    rhash.resize(n + 1, 0);
    powr[0] = 1, fhash[0] = s[0] - 'a' + 1;
    rhash[n - 1] = s[n - 1] - 'a' + 1;
    for (long long int i = 1; i < n; i++) {
      powr[i] = (powr[i - 1] * p) % 1000000007;
      fhash[i] =
          ((fhash[i - 1] * p) % 1000000007 + (s[i] - 'a' + 1)) % 1000000007;
      rhash[n - 1 - i] =
          ((rhash[n - i] * p) % 1000000007 + s[n - i - 1] - 'a' + 1) %
          1000000007;
    }
  }
  long long int frontHash(long long int i, long long int j) {
    if (i == 0) return fhash[j];
    long long int hashvalue =
        (fhash[j] - (fhash[i - 1] * powr[j - i + 1]) % 1000000007 +
         1000000007) %
        1000000007;
    return hashvalue;
  }
  long long int reverseHash(long long int i, long long int j) {
    if (j == n - 1) return rhash[i];
    long long int hashvalue =
        (rhash[i] - (rhash[j + 1] * powr[j - i + 1]) % 1000000007 +
         1000000007) %
        1000000007;
    return hashvalue;
  }
  bool isPalindrome(long long int i, long long int j) {
    long long int len = (j - i + 1) / 2;
    long long int fhashh, rhashh;
    fhashh = frontHash(i, i + len - 1);
    if ((j - i + 1) % 2) {
      rhashh = reverseHash(len + 1 + i, 2 * len + i);
    } else {
      rhashh = reverseHash(len + i, 2 * len - 1 + i);
    }
    return fhashh == rhashh ? true : false;
  }
};
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  string s;
  cin >> s;
  Hash kp(s);
  long long int n = s.size();
  long long int dp[n][n];
  memset(dp, 0, sizeof dp);
  for (long long int i = 0; i < n; ++i) dp[i][i] = 1;
  vector<long long int> ans(n + 1, 0);
  ans[1] += n;
  for (long long int len = 2; len <= n; ++len) {
    for (long long int i = 0; i + len - 1 < n; ++i) {
      if (kp.isPalindrome(i, i + len - 1)) {
        long long int h = len / 2;
        h--;
        dp[i][i + len - 1] = dp[i][i + h] + 1LL;
        for (long long int k = dp[i][i + len - 1]; k >= 1; k--) ans[k]++;
      }
    }
  }
  for (long long int i = 1; i <= n; ++i) cout << ans[i] << " ";
}