#include <bits/stdc++.h>
using namespace std;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
int C = 26;
int n;
char s[300005];
int nxt[30][300005];
int pos[30];
long long int res[30];
int main() {
  scanf("%s", s);
  n = strlen(s);
  for (int i = 0; i < (C); ++i) nxt[i][n] = n;
  for (int i = n - 1; i >= 0; --i) {
    for (int j = 0; j < (C); ++j) {
      nxt[j][i] = nxt[j][i + 1];
      if (s[i] - 'a' == j) nxt[j][i] = i;
      pos[j] = nxt[j][i];
    }
    pos[C] = n;
    sort(pos, pos + C + 1);
    for (int j = 0; j < (C); ++j) {
      res[j + 1] += pos[j + 1] - pos[j];
    }
  }
  int diver = 0;
  for (int j = 0; j < (C + 1); ++j)
    if (res[j] > 0) diver = j;
  cout << diver << endl;
  for (int j = 0; j < (diver); ++j) cout << res[j + 1] << endl;
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
int C = 26;
int n;
char s[300005];
int nxt[30][300005];
int pos[30];
long long int res[30];
int main() {
  scanf("%s", s);
  n = strlen(s);
  for (int i = 0; i < (C); ++i) nxt[i][n] = n;
  for (int i = n - 1; i >= 0; --i) {
    for (int j = 0; j < (C); ++j) {
      nxt[j][i] = nxt[j][i + 1];
      if (s[i] - 'a' == j) nxt[j][i] = i;
      pos[j] = nxt[j][i];
    }
    pos[C] = n;
    sort(pos, pos + C + 1);
    for (int j = 0; j < (C); ++j) {
      res[j + 1] += pos[j + 1] - pos[j];
    }
  }
  int diver = 0;
  for (int j = 0; j < (C + 1); ++j)
    if (res[j] > 0) diver = j;
  cout << diver << endl;
  for (int j = 0; j < (diver); ++j) cout << res[j + 1] << endl;
  return 0;
}

```