Разнообразностью строки назовем количество различных символов, которые в ней встречаются хотя бы один раз. Разнообразность строки s будем обозначать как d(s). К примеру, d('aaa') = 1, d('abacaba') = 3. Пусть задана строка s, состоящая из строчных символов латинского алфавита. Рассмотрим все ее подстроки. Очевидно, что разнообразность любой подстроки — это число от 1 до d(s). Выдайте статистику разнообразности подстрок, посчитав для каждого k от 1 до d(s), сколько подстрок строки s имеет разнообразность ровно k.
Выходные данные
В первой строке выведите d(s) — разнообразность строки s. Далее выведите d(s) строк. В k-й из этих строк выведите количество подстрок строки s, имеющих разнообразность k.
Примечание
Рассмотрим первый пример. Обозначим через s(i, j) подстроку строки 'abca' с символа номер 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
Всего количество подстрок с разнообразностью 1 равно 4, с разнообразностью 2 равно 3, с разнообразностью 3 равно 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abca
|
3
4
3
3
|
|
2
|
aabacaabbad
|
4
14
19
28
5
|