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;
int main() {
  int m, n, l1, r1, l2, r2, sm;
  string s;
  cin >> s;
  n = s.size();
  long long x;
  const long long p1 = 713;
  const long long m1 = 1000000007;
  const long long p2 = 731;
  const long long m2 = 1000000009;
  vector<long long> pd1(n + 1);
  x = 1;
  for (int i = 0; i <= n; i++) {
    pd1[i] = x;
    x = (x * p1) % m1;
  }
  vector<long long> pd2(n + 1);
  x = 1;
  for (int i = 0; i <= n; i++) {
    pd2[i] = x;
    x = (x * p2) % m2;
  }
  vector<long long> h1(n + 1);
  h1[0] = 0;
  for (int i = 1; i <= n; i++) {
    h1[i] = (h1[i - 1] * p1 + s[i - 1]) % m1;
  }
  vector<long long> h2(n + 1);
  h2[0] = 0;
  for (int i = 1; i <= n; i++) {
    h2[i] = (h2[i - 1] * p2 + s[i - 1]) % m2;
  }
  vector<vector<int>> d(n + 1, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= min(i, n - i - 1); j++) {
      if (s[i - j] != s[i + j]) {
        break;
      }
      d[2 * j + 1][i] = 1;
    }
    for (int j = 1; j <= min(i + 1, n - i - 1); j++) {
      if (s[i - j + 1] != s[i + j]) {
        break;
      }
      d[2 * j][i] = 1;
    }
  }
  for (int i = 2; i <= n; i++) {
    if (i % 2 == 0) {
      for (int j = (i / 2) - 1; j < n - (i / 2); j++) {
        l1 = j - (i / 2) + 2;
        r1 = j + 1;
        l2 = j + 2;
        r2 = j + (i / 2) + 1;
        if ((r2 - l2 == r1 - l1) &&
            (h1[r1] + m1 - (((h1[l1 - 1] * pd1[r1 - l1 + 1])) % m1)) % m1 ==
                (h1[r2] + m1 - (((h1[l2 - 1] * pd1[r2 - l2 + 1])) % m1)) % m1 &&
            (h2[r1] + m2 - (((h2[l1 - 1] * pd2[r1 - l1 + 1])) % m2)) % m2 ==
                (h2[r2] + m2 - ((h2[l2 - 1] * pd2[r2 - l2 + 1]) % m2)) % m2) {
          if ((i / 2) % 2 == 0) {
            if (d[i / 2][j - (i / 4)] != 0) d[i][j] = d[i / 2][j - (i / 4)] + 1;
          } else {
            if (d[i / 2][j - ((i / 2) - 1) / 2] != 0)
              d[i][j] = d[i / 2][j - ((i / 2) - 1) / 2] + 1;
          }
        }
      }
    } else {
      for (int j = (i - 1) / 2; j < n - ((i - 1) / 2); j++) {
        l1 = j - ((i - 1) / 2) + 1;
        r1 = j;
        l2 = j + 2;
        r2 = j + ((i - 1) / 2) + 1;
        if ((r2 - l2 == r1 - l1) &&
            (h1[r1] + m1 - (((h1[l1 - 1] * pd1[r1 - l1 + 1])) % m1)) % m1 ==
                (h1[r2] + m1 - (((h1[l2 - 1] * pd1[r2 - l2 + 1])) % m1)) % m1 &&
            (h2[r1] + m2 - (((h2[l1 - 1] * pd2[r1 - l1 + 1])) % m2)) % m2 ==
                (h2[r2] + m2 - ((h2[l2 - 1] * pd2[r2 - l2 + 1]) % m2)) % m2) {
          if (((i - 1) / 2) % 2 == 0) {
            if (d[(i - 1) / 2][j - ((i - 1) / 4) - 1] != 0)
              d[i][j] = d[(i - 1) / 2][j - ((i - 1) / 4) - 1] + 1;
          } else {
            if (d[(i - 1) / 2][j - ((((i - 1) / 2) - 1) / 2) - 1] != 0)
              d[i][j] = d[(i - 1) / 2][j - ((((i - 1) / 2) - 1) / 2) - 1] + 1;
          }
        }
      }
    }
  }
  vector<int> b(n);
  sm = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < n; j++) {
      if (d[i][j] != 0) {
        b[d[i][j] - 1]++;
      }
    }
  }
  vector<int> ans(n);
  for (int i = n - 1; i >= 0; i--) {
    sm += b[i];
    ans[i] = sm;
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << ' ';
  }
  return 0;
}