% Origin: 20091014, SPbSU Group A1 Fourth Training - Greedy Algorithms
% Author: Ivan Kazmenko (classic)
% Text Author: Ivan Kazmenko
% Tests Author: Ivan Kazmenko

\begin{problem}{Кодирование}
{encoding.in}{encoding.out}
{2 секунды}{256 Мебибайт}

Известно, что в текстах практически на любом языке, имеющем алфавит,
одни буквы систематически встречаются чаще, чем другие. Например,
в типичном тексте на английском языке частота буквы `e' больше двенадцати
процентов, а частота буквы `z' меньше одного процента. В русском языке
буква `о' имеет частоту более девяти процентов,
а буква `ъ' "--- менее одной десятой процента.

Такие различия между буквами можно использовать, чтобы хранить
тексты в сжатом виде. Сопоставим каждой букве какой-то непустой двоичный код;
частым буквам сопоставим коды из малого количества битов, а редким "---
из большого количества битов. Строку будем записывать как последовательность
кодов букв в ней без разделитетей. Коды букв организуем таким образом, чтобы
ни один код буквы не начинался с кода какой-то другой буквы; такие коды
называются \textit{беспрефиксными}. К примеру, если мы закодируем букву `e'
кодом \t{10}, то все остальные буквы должны иметь либо код \t{0}, либо код,
начинающийся на \t{00}, \t{01} или \t{11}. Это нужно для того, чтобы
в закодированном тексте не требовалось ставить разделители между буквами:
при такой организации кодов любая закодированная строка восстанавливается
однозначно.

От того, какие коды букв мы выберем, зависит размер закодированной строки.
Например, если в строке ``\t{abacabad}'' мы закодируем буквы как
``\t{a: 00}'', ``\t{b: 01}'', ``\t{c: 10}'' и ``\t{d: 11}'', то закодированная
строка будет иметь вид ``\t{00\,01\,00\,10\,00\,01\,00\,11}'' (группы цифр,
соответствующие разным буквам, разделены для удобства восприятия),
и размер её будет равен 16.
Если же мы выберем другие беспрефиксные коды ``\t{a: 0}'', ``\t{b: 10}'',
``\t{c: 110}'' и ``\t{d: 111}'', то закодированная строка будет иметь вид
``\t{0\,10\,0\,110\,0\,10\,0\,111}'', и её размер будет равен 14.

Дана строка $s$. Сопоставьте каждой её букве двоичный код так,
чтобы коды букв были беспрефиксными, и при этом закодированная ими
строка $s$ имела минимальный возможный размер.

\InputFile

В первой строке входного файла задана непустая строка $s$.
Она состоит из строчных букв латинского алфавита.
Длина этой строки не превосходит $100\,000$ символов.

\OutputFile

В первой строке выходного файла выведите два числа $k$ и $l$ через
пробел "--- количество различных букв, встречающихся в строке,
и размер получившейся закодированной строки, соответственно.
В следующих $k$ строках запишите коды букв в формате
``\t{<letter>: <code>}''. Ни один код не должен являться префиксом другого.
Буквы могут быть перечислены в любом порядке.
Наконец, в последней строке запишите закодированную строку.

Если ответов с минимальным значением $l$ несколько, можно вывести
любой из них.

\Examples

\begin{example}
\exmp{
a
}{
1 1
a: 0
0
}%
\exmp{
abacabad
}{
4 14
a: 0
b: 10
c: 110
d: 111
01001100100111
}%
\end{example}
\end{problem}
