#include <bits/stdc++.h>
using namespace std;
const int N = 333333;
string str;
int n;
struct SegmentTree {
  int mask[N << 2];
  void build(int p, int l, int r) {
    if (l == r) {
      mask[p] = 1 << (str[l] - 'a');
      return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    mask[p] = mask[p << 1] | mask[p << 1 | 1];
  }
  int query(int p, int l, int r, int L, int R, int m) {
    if (L > R) return n;
    if (L <= l && r <= R && (m & mask[p]) == 0) return n;
    if (l == r) {
      return l;
    }
    int mid = l + r >> 1;
    int res = n;
    if (L <= mid) {
      res = min(res, query(p << 1, l, mid, L, R, m));
    }
    if (res < n) return res;
    if (mid < R) {
      res = min(res, query(p << 1 | 1, mid + 1, r, L, R, m));
    }
    return res;
  }
} st;
long long counter[30];
int main() {
  cin >> str;
  n = str.length();
  int mask = 0;
  for (int i = 0; i < str.length(); i++) {
    mask |= 1 << (str[i] - 'a');
  }
  int cnt = 0;
  for (int i = 0; i < 26; i++) {
    if (mask >> i & 1) cnt++;
  }
  cout << cnt << endl;
  st.build(1, 0, n - 1);
  memset(counter, 0, sizeof(counter));
  for (int i = 0; i < str.length(); i++) {
    int pre, now = i;
    int m = (1 << 26) - 1;
    int t = 0;
    while (now < n) {
      m ^= (1 << (str[now] - 'a'));
      t++;
      pre = now, now = st.query(1, 0, n - 1, now + 1, n - 1, m);
      counter[t] += now - pre;
    }
  }
  for (int i = 1; i <= cnt; i++) cout << counter[i] << endl;
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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;
const int N = 333333;
string str;
int n;
struct SegmentTree {
  int mask[N << 2];
  void build(int p, int l, int r) {
    if (l == r) {
      mask[p] = 1 << (str[l] - 'a');
      return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    mask[p] = mask[p << 1] | mask[p << 1 | 1];
  }
  int query(int p, int l, int r, int L, int R, int m) {
    if (L > R) return n;
    if (L <= l && r <= R && (m & mask[p]) == 0) return n;
    if (l == r) {
      return l;
    }
    int mid = l + r >> 1;
    int res = n;
    if (L <= mid) {
      res = min(res, query(p << 1, l, mid, L, R, m));
    }
    if (res < n) return res;
    if (mid < R) {
      res = min(res, query(p << 1 | 1, mid + 1, r, L, R, m));
    }
    return res;
  }
} st;
long long counter[30];
int main() {
  cin >> str;
  n = str.length();
  int mask = 0;
  for (int i = 0; i < str.length(); i++) {
    mask |= 1 << (str[i] - 'a');
  }
  int cnt = 0;
  for (int i = 0; i < 26; i++) {
    if (mask >> i & 1) cnt++;
  }
  cout << cnt << endl;
  st.build(1, 0, n - 1);
  memset(counter, 0, sizeof(counter));
  for (int i = 0; i < str.length(); i++) {
    int pre, now = i;
    int m = (1 << 26) - 1;
    int t = 0;
    while (now < n) {
      m ^= (1 << (str[now] - 'a'));
      t++;
      pre = now, now = st.query(1, 0, n - 1, now + 1, n - 1, m);
      counter[t] += now - pre;
    }
  }
  for (int i = 1; i <= cnt; i++) cout << counter[i] << endl;
  return 0;
}

```