#include <bits/stdc++.h>
namespace io {
const int size = 1 << 20;
char buf[size], puf[size], d[20], *p = puf, *p1, *p2;
template <class type>
void inline read(type &a) {
  int f = 1,
      c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
               ? EOF
               : *p1++);
  for (; !(c >= 48 && c <= 59);
       f = c == 45 ? -1 : 1,
       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++))
    ;
  for (a = 0; (c >= 48 && c <= 59); a *= 10, a += c ^ 48,
      c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
               ? EOF
               : *p1++))
    ;
  a *= f;
}
void inline readstr(std::string &s) {
  char c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++);
  for (; !(c >= 97 && c <= 122);
       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++))
    ;
  for (; (c >= 97 && c <= 122);
       s += c,
       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++))
    ;
}
template <class type>
void inline write(type a, char c = '\n') {
  int s = d[0] = 0;
  for (a < 0 ? a = -a,
               (*p++ = 45,
               p - puf == size ? (fwrite(puf, 1, p - puf, stdout), p = puf) : 0)
             : 0;
       a; d[s++] = a % 10, a /= 10)
    ;
  for (s = s ? s : 1; s;
       (*p++ = d[--s] + 48,
       p - puf == size ? (fwrite(puf, 1, p - puf, stdout), p = puf) : 0))
    ;
  (*p++ = c, p - puf == size ? (fwrite(puf, 1, p - puf, stdout), p = puf) : 0);
}
}  // namespace io
using namespace io;
using namespace std;
const int nsz = 3e5, lgsz = 18, asz = 26, msksz = (1 << (asz / 2)) - 1;
int n, m, a[nsz + 5], cnt[msksz + 5], pos[asz + 5];
long long ans[asz + 5];
string s;
struct sparse_table {
  int lg[nsz + 5], st[nsz + 5][lgsz + 5];
  void inline init(int a[]) {
    for (int i = 1; i <= n; ++i) {
      lg[i] = lg[i >> 1] + 1;
      st[i][0] = 1 << a[i];
    }
    for (int k = 1; k <= lgsz; ++k) {
      for (int i = 1; i <= n; ++i) {
        int len = 1 << (k - 1);
        if (i + len - 1 > n) break;
        st[i][k] = st[i][k - 1] | st[i + len][k - 1];
      }
    }
  }
  int inline qry(int l, int r) {
    int k = lg[r - l + 1] - 1, len = 1 << k;
    return st[l][k] | st[r - len + 1][k];
  }
};
sparse_table st;
void inline init() {
  for (int S = 1; S <= msksz; ++S) {
    cnt[S] = cnt[S - (S & -S)] + 1;
  }
}
int inline calc(int l, int r) {
  int S = st.qry(l, r), S1 = S >> 13, S2 = S - (S1 << 13);
  return cnt[S1] + cnt[S2];
}
void inline solve(int p) {
  int mx = calc(p, n), pre = p - 1;
  for (int c = 1; c <= mx; ++c) {
    int l = pre, r = pos[c + 1] + 1, md = (l + r) >> 1;
    for (; r - l > 1; md = (l + r) >> 1) {
      (calc(p, md) <= c ? l : r) = md;
    }
    ans[c] += l - pre;
    pre = l;
    pos[c] = l;
  }
}
int main() {
  init();
  readstr(s);
  n = (int)s.size();
  for (int i = 0; i < n; ++i) {
    a[i + 1] = s[i] - 97;
  }
  st.init(a);
  m = calc(1, n);
  for (int i = 1; i <= m + 1; ++i) {
    pos[i] = n;
  }
  for (int i = 1; i <= n; ++i) {
    solve(i);
  }
  write(m);
  for (int i = 1; i <= m; ++i) {
    write(ans[i]);
  }
  (fwrite(puf, 1, p - puf, stdout), p = puf);
}

### 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>
namespace io {
const int size = 1 << 20;
char buf[size], puf[size], d[20], *p = puf, *p1, *p2;
template <class type>
void inline read(type &a) {
  int f = 1,
      c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
               ? EOF
               : *p1++);
  for (; !(c >= 48 && c <= 59);
       f = c == 45 ? -1 : 1,
       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++))
    ;
  for (a = 0; (c >= 48 && c <= 59); a *= 10, a += c ^ 48,
      c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
               ? EOF
               : *p1++))
    ;
  a *= f;
}
void inline readstr(std::string &s) {
  char c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++);
  for (; !(c >= 97 && c <= 122);
       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++))
    ;
  for (; (c >= 97 && c <= 122);
       s += c,
       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2)
                ? EOF
                : *p1++))
    ;
}
template <class type>
void inline write(type a, char c = '\n') {
  int s = d[0] = 0;
  for (a < 0 ? a = -a,
               (*p++ = 45,
               p - puf == size ? (fwrite(puf, 1, p - puf, stdout), p = puf) : 0)
             : 0;
       a; d[s++] = a % 10, a /= 10)
    ;
  for (s = s ? s : 1; s;
       (*p++ = d[--s] + 48,
       p - puf == size ? (fwrite(puf, 1, p - puf, stdout), p = puf) : 0))
    ;
  (*p++ = c, p - puf == size ? (fwrite(puf, 1, p - puf, stdout), p = puf) : 0);
}
}  // namespace io
using namespace io;
using namespace std;
const int nsz = 3e5, lgsz = 18, asz = 26, msksz = (1 << (asz / 2)) - 1;
int n, m, a[nsz + 5], cnt[msksz + 5], pos[asz + 5];
long long ans[asz + 5];
string s;
struct sparse_table {
  int lg[nsz + 5], st[nsz + 5][lgsz + 5];
  void inline init(int a[]) {
    for (int i = 1; i <= n; ++i) {
      lg[i] = lg[i >> 1] + 1;
      st[i][0] = 1 << a[i];
    }
    for (int k = 1; k <= lgsz; ++k) {
      for (int i = 1; i <= n; ++i) {
        int len = 1 << (k - 1);
        if (i + len - 1 > n) break;
        st[i][k] = st[i][k - 1] | st[i + len][k - 1];
      }
    }
  }
  int inline qry(int l, int r) {
    int k = lg[r - l + 1] - 1, len = 1 << k;
    return st[l][k] | st[r - len + 1][k];
  }
};
sparse_table st;
void inline init() {
  for (int S = 1; S <= msksz; ++S) {
    cnt[S] = cnt[S - (S & -S)] + 1;
  }
}
int inline calc(int l, int r) {
  int S = st.qry(l, r), S1 = S >> 13, S2 = S - (S1 << 13);
  return cnt[S1] + cnt[S2];
}
void inline solve(int p) {
  int mx = calc(p, n), pre = p - 1;
  for (int c = 1; c <= mx; ++c) {
    int l = pre, r = pos[c + 1] + 1, md = (l + r) >> 1;
    for (; r - l > 1; md = (l + r) >> 1) {
      (calc(p, md) <= c ? l : r) = md;
    }
    ans[c] += l - pre;
    pre = l;
    pos[c] = l;
  }
}
int main() {
  init();
  readstr(s);
  n = (int)s.size();
  for (int i = 0; i < n; ++i) {
    a[i + 1] = s[i] - 97;
  }
  st.init(a);
  m = calc(1, n);
  for (int i = 1; i <= m + 1; ++i) {
    pos[i] = n;
  }
  for (int i = 1; i <= n; ++i) {
    solve(i);
  }
  write(m);
  for (int i = 1; i <= m; ++i) {
    write(ans[i]);
  }
  (fwrite(puf, 1, p - puf, stdout), p = puf);
}

```