#include <bits/stdc++.h>
using namespace std;
template <class T>
void PVecPrint(vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++)
    cout << v[i].first << "," << v[i].second << ' ';
  cout << '\n';
}
template <class T>
void VecPrint(vector<T> &v) {
  for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
  cout << '\n';
}
string s;
vector<vector<int> > v(26);
int n;
struct FenwickTree {
  vector<int> bit;
  int n;
  void build(vector<int> &a) {
    n = a.size();
    bit.resize(n);
    for (int i = 0; i < a.size(); i++) add(i, a[i]);
  }
  int sum(int r) {
    int ret = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
    return ret;
  }
  int sum(int l, int r) { return sum(r) - sum(l - 1); }
  void add(int idx, int delta) {
    for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
  }
};
FenwickTree F;
int getVal(int l, int r) { return F.sum(l, r); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> s;
  n = s.length();
  for (int i = 0; i < n; i++) {
    int id = s[i] - 'a';
    v[id].push_back(i);
  }
  vector<int> temp(n, 0);
  F.build(temp);
  vector<int> imp(26, -1);
  vector<long long int> res(27, 0);
  vector<int> pval(27, 0);
  pval[1] = 1;
  res[1] += 1;
  int id = s[0] - 'a';
  imp[id] = 0;
  F.add(0, 1);
  int l1, r1;
  for (int i = 1; i < n; i++) {
    int x = s[i] - 'a';
    if (imp[x] == -1) {
      imp[x] = i;
      l1 = 0;
      F.add(i, 1);
    } else {
      F.add(imp[x], -1);
      l1 = imp[x] + 1;
      imp[x] = i;
      F.add(i, 1);
    }
    int r1 = i - 1;
    int mval = getVal(l1, r1), prev = i;
    vector<int> pval1(27, 0);
    pval1[1] = 1;
    res[1] += 1;
    for (int j = 1; j <= mval; j++) {
      int ans, l = l1, r = prev - 1;
      for (int k = 0; k < 30; k++) {
        if (l == r) {
          ans = l;
          break;
        } else if (r == l + 1) {
          int t = getVal(l, i - 1);
          if (t == j)
            ans = l;
          else
            ans = r;
          break;
        }
        int mid = (l + r) / 2;
        int t = getVal(mid, i - 1);
        if (t > j)
          l = mid;
        else
          r = mid;
      }
      res[j + 1] += (prev - ans);
      pval[j] -= (prev - ans);
      pval1[j + 1] += (prev - ans);
      prev = ans;
    }
    for (int k = 0; k < 27; k++) res[k] += pval[k];
    for (int k = 0; k < 27; k++) pval[k] += pval1[k];
  }
  for (int i = 26; i > -1; i--) {
    if (res[i] > 0) {
      cout << i << '\n';
      break;
    }
  }
  for (int i = 1; i <= 26; i++) {
    if (res[i] == 0) break;
    cout << res[i] << '\n';
  }
}

### Prompt

Develop a solution in CPP to the problem described below:

String diversity is the number of symbols that occur in the string at least once. Diversity of s will be denoted by d(s). For example , d("aaa")=1, d("abacaba")=3.

Given a string s, consisting of lowercase Latin letters. Consider all its substrings. Obviously, any substring diversity is a number from 1 to d(s). Find statistics about substrings diversity: for each k from 1 to d(s), find how many substrings of s has a diversity of exactly k.

Input

The input consists of a single line containing s. It contains only lowercase Latin letters, the length of s is from 1 to 3·105.

Output

Print to the first line the value d(s). Print sequence t1, t2, ..., td(s) to the following lines, where ti is the number of substrings of s having diversity of exactly i.

Examples

Input

abca


Output

3
4
3
3


Input

aabacaabbad


Output

4
14
19
28
5

Note

Consider the first example.

We denote by s(i, j) a substring of "abca" with the indices in the segment [i, j].

  * s(1, 1) =  "a", d("a") = 1
  * s(2, 2) =  "b", d("b") = 1
  * s(3, 3) =  "c", d("c") = 1
  * s(4, 4) =  "a", d("a") = 1
  * s(1, 2) =  "ab", d("ab") = 2
  * s(2, 3) =  "bc", d("bc") = 2
  * s(3, 4) =  "ca", d("ca") = 2
  * s(1, 3) =  "abc", d("abc") = 3
  * s(2, 4) =  "bca", d("bca") = 3
  * s(1, 4) =  "abca", d("abca") = 3



Total number of substring with diversity 1 is 4, with diversity 2 equals 3, 3 diversity is 3.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
void PVecPrint(vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++)
    cout << v[i].first << "," << v[i].second << ' ';
  cout << '\n';
}
template <class T>
void VecPrint(vector<T> &v) {
  for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
  cout << '\n';
}
string s;
vector<vector<int> > v(26);
int n;
struct FenwickTree {
  vector<int> bit;
  int n;
  void build(vector<int> &a) {
    n = a.size();
    bit.resize(n);
    for (int i = 0; i < a.size(); i++) add(i, a[i]);
  }
  int sum(int r) {
    int ret = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
    return ret;
  }
  int sum(int l, int r) { return sum(r) - sum(l - 1); }
  void add(int idx, int delta) {
    for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
  }
};
FenwickTree F;
int getVal(int l, int r) { return F.sum(l, r); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> s;
  n = s.length();
  for (int i = 0; i < n; i++) {
    int id = s[i] - 'a';
    v[id].push_back(i);
  }
  vector<int> temp(n, 0);
  F.build(temp);
  vector<int> imp(26, -1);
  vector<long long int> res(27, 0);
  vector<int> pval(27, 0);
  pval[1] = 1;
  res[1] += 1;
  int id = s[0] - 'a';
  imp[id] = 0;
  F.add(0, 1);
  int l1, r1;
  for (int i = 1; i < n; i++) {
    int x = s[i] - 'a';
    if (imp[x] == -1) {
      imp[x] = i;
      l1 = 0;
      F.add(i, 1);
    } else {
      F.add(imp[x], -1);
      l1 = imp[x] + 1;
      imp[x] = i;
      F.add(i, 1);
    }
    int r1 = i - 1;
    int mval = getVal(l1, r1), prev = i;
    vector<int> pval1(27, 0);
    pval1[1] = 1;
    res[1] += 1;
    for (int j = 1; j <= mval; j++) {
      int ans, l = l1, r = prev - 1;
      for (int k = 0; k < 30; k++) {
        if (l == r) {
          ans = l;
          break;
        } else if (r == l + 1) {
          int t = getVal(l, i - 1);
          if (t == j)
            ans = l;
          else
            ans = r;
          break;
        }
        int mid = (l + r) / 2;
        int t = getVal(mid, i - 1);
        if (t > j)
          l = mid;
        else
          r = mid;
      }
      res[j + 1] += (prev - ans);
      pval[j] -= (prev - ans);
      pval1[j + 1] += (prev - ans);
      prev = ans;
    }
    for (int k = 0; k < 27; k++) res[k] += pval[k];
    for (int k = 0; k < 27; k++) pval[k] += pval1[k];
  }
  for (int i = 26; i > -1; i--) {
    if (res[i] > 0) {
      cout << i << '\n';
      break;
    }
  }
  for (int i = 1; i <= 26; i++) {
    if (res[i] == 0) break;
    cout << res[i] << '\n';
  }
}

```