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;
string s;
int dp[5003][5003], ans[5003], rash[5003][5003];
int palindromo(int i, int j) {
  if (i >= j) return true;
  if (dp[i][j] != -1) return dp[i][j];
  if (s[i] == s[j] && palindromo(i + 1, j - 1)) return dp[i][j] = true;
  return dp[i][j] = false;
}
void init() {
  for (int i = 0; i < ((int)(s).size()); i++) s[i] -= 'a';
  for (int i = 0; i < ((int)(s).size()); i++) {
    long long sum = 0, pot = 1;
    long long sum2 = 0, pot2 = 1;
    for (int j = i; j < ((int)(s).size()); j++) {
      sum += (pot * s[j]) % 1000000009LL;
      pot = (pot * 37LL) % 1000000009LL;
      ;
      rash[i][j - i + 1] = sum;
    }
  }
}
void add(int i, int j) {
  long long cnt = 1, tam;
  while (i <= j) {
    if (palindromo(i, j)) ans[cnt]++;
    if (i == j) break;
    tam = (j - i + 1) / 2;
    if (rash[i][tam] != rash[j - tam + 1][tam]) break;
    j = i + tam - 1;
    cnt++;
  }
}
int main() {
  memset(dp, -1, sizeof(dp));
  cin >> s;
  init();
  for (int i = 0; i < ((int)(s).size()); i++) {
    for (int j = i; j < ((int)(s).size()); j++) {
      add(i, j);
    }
  }
  for (int i = 1; i < ((int)(s).size()) + 1; i++) cout << ans[i] << " ";
  cout << endl;
}