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;
void get_check(string s, vector<vector<bool>> &check) {
  for (int i = 0; i <= (int)((s).size()) - 1; i++) {
    check[i][i] = 1;
  }
  for (int l = 2; l <= (int)((s).size()); l++) {
    for (int i = 0; i <= (int)((s).size()) - l; i++) {
      int j = i + l - 1;
      if (s[i] == s[j])
        if ((check[i + 1][j - 1]) || (i + 1 == j)) {
          check[i][j] = true;
        }
    }
  }
}
vector<int> z_array(string s) {
  vector<int> ans((int)((s).size()));
  ans[0] = -1;
  int l = 0, r = 0;
  for (int i = 1; i < s.size(); i++) {
    if (i > r) {
      l = i;
      r = i;
      while ((r < s.size()) && (s[r] == s[r - i])) {
        r++;
      }
      r--;
      ans[i] = r - l + 1;
    } else {
      int k = i - l;
      if (ans[k] + i <= r) {
        ans[i] = ans[k];
      } else {
        l = i;
        while ((r < s.size()) && (s[r] == s[r - i])) {
          r++;
        }
        r--;
        ans[i] = r - l + 1;
      }
    }
  }
  return ans;
}
int main() {
  {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  }
  string s;
  cin >> s;
  vector<vector<int>> rep((int)((s).size()), vector<int>((int)((s).size()), 0));
  for (int i = 0; i <= (int)((s).size()) - 1; i++) {
    string imps = s.substr(i, (int)((s).size()) - i) + "*" + s;
    vector<int> imparr = z_array(imps);
    for (int j = i; j <= (int)((s).size()) - 1; j++) {
      rep[i][j] = imparr[j + (int)((s).size()) - i + 1];
    }
  }
  vector<vector<int>> order((int)((s).size()),
                            vector<int>((int)((s).size()), 0));
  vector<int> ans((int)((s).size()), 0);
  for (int i = 0; i <= (int)((s).size()) - 1; i++) {
    order[i][i] = 1;
    ans[0]++;
  }
  for (int l = 2; l <= (int)((s).size()); l++) {
    for (int i = 0; i <= (int)((s).size()) - l; i++) {
      int j = i + l - 1;
      if (s[i] == s[j]) {
        if (order[i + 1][j - 1]) {
          int mid = (i + j + 2) / 2;
          if (rep[i][mid] >= l / 2)
            order[i][j] = order[mid][j] + 1;
          else {
            order[i][j] = 1;
          }
          ans[order[i][j] - 1]++;
        }
        if (i + 1 == j) {
          order[i][j] = 2;
          ans[order[i][j] - 1]++;
        }
      }
    }
  }
  for (int i = (int)((s).size()) - 2; i >= 0; i--) {
    ans[i] = ans[i + 1] + ans[i];
  };
  for (int i = 0; i < (int)((s).size()); i++) cout << ans[i] << ' ';
  ;
  cout << "\n";
}