CF386C.Diverse Substrings

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.

字符串的多样性是指在该字符串中至少出现一次的不同字符的个数。字符串 $s$ 的多样性记作 $d(s)$。例如，$d(\text{“aaa”}) = 1$，$d(\text{“abacaba”}) = 3$。

给定一个由小写拉丁字母组成的字符串 $s$。考虑 $s$ 的所有子串。显然，任意子串的多样性均为 $1$ 到 $d(s)$ 之间的整数。请统计各子串的多样性：对每个 $k$（$k$ 从 $1$ 到 $d(s)$），求出 $s$ 中恰好具有 $k$ 种多样性的子串个数。

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.

输入仅包含一行，内容为字符串 $s$。$s$ 仅由小写拉丁字母组成，其长度在 $1$ 到 $3 \cdot 10^5$ 之间。

Print to the first line the value d(s). Print sequence _t_1, _t_2, ..., t__d(s) to the following lines, where t__i is the number of substrings of s having diversity of exactly i.

第一行输出值 $d(s)$。接下来的若干行输出序列 $t_1,\ t_2,\ \dots,\ t_{d(s)}$，其中 $t_i$ 表示字符串 $s$ 中恰好具有多样性 $i$ 的子串个数。

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.

考虑第一个例子。

我们用 $s(i, j)$ 表示字符串 "abca" 中下标在区间 $[i, j]$ 内的子串。

• $s(1, 1) = \text{"a"}$，$d(\text{"a"}) = 1$
• $s(2, 2) = \text{"b"}$，$d(\text{"b"}) = 1$
• $s(3, 3) = \text{"c"}$，$d(\text{"c"}) = 1$
• $s(4, 4) = \text{"a"}$，$d(\text{"a"}) = 1$
• $s(1, 2) = \text{"ab"}$，$d(\text{"ab"}) = 2$
• $s(2, 3) = \text{"bc"}$，$d(\text{"bc"}) = 2$
• $s(3, 4) = \text{"ca"}$，$d(\text{"ca"}) = 2$
• $s(1, 3) = \text{"abc"}$，$d(\text{"abc"}) = 3$
• $s(2, 4) = \text{"bca"}$，$d(\text{"bca"}) = 3$
• $s(1, 4) = \text{"abca"}$，$d(\text{"abca"}) = 3$

多样性为 1 的子串总数为 4，多样性为 2 的子串总数为 3，多样性为 3 的子串总数为 3。