C. Разнообразные подстроки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Разнообразностью строки назовем количество различных символов, которые в ней встречаются хотя бы один раз. Разнообразность строки s будем обозначать как d(s). К примеру, d('aaa') = 1,  d('abacaba') = 3. Пусть задана строка s, состоящая из строчных символов латинского алфавита. Рассмотрим все ее подстроки. Очевидно, что разнообразность любой подстроки — это число от 1 до d(s). Выдайте статистику разнообразности подстрок, посчитав для каждого k от 1 до d(s), сколько подстрок строки s имеет разнообразность ровно k.

Входные данные

Входные данные состоят из единственной строки. В ней записана последовательность строчных букв латинского алфавита — строка s длиной от 1 до 3·105.

Выходные данные

В первой строке выведите d(s) — разнообразность строки s. Далее выведите d(s) строк. В k-й из этих строк выведите количество подстрок строки s, имеющих разнообразность k.

Примеры
Входные данные
abca
Выходные данные
3
4
3
3
Входные данные
aabacaabbad
Выходные данные
4
14
19
28
5
Примечание

Рассмотрим первый пример. Обозначим через 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.