背景

哈夫曼编码，又称为赫夫曼编码（Huffman Coding），是一种可变长编码（ VLC, variable length coding)）方式，比起定长编码的 ASCII 编码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的；是一种用于无损数据压缩的熵编码算法，通常用于压缩重复率比较高的字符数据。 哈夫曼编码首先会使用字符的频率创建一棵树，然后通过这个树的结构为每个字符生成一个特定的编码，出现频率高的字符使用较短的编码，出现频率低的则使用较长的编码，这样就会使编码之后的字符串平均长度降低，从而达到数据无损压缩的目的。 一种编码方式如下： 将字符串 BCAADDDCCACACAC 通过以下方式编码。

1. 计算字符串中每个字符的频率；

2. 按照字符出现的频率进行排序，组成一个队列 Q，出现频率最低的在前面，出现频率高的在后面，相同时按字典序排列；

3. 把这些字符作为叶子节点开始构建一颗哈夫曼树；

• （1）首先创建一个空节点 z，将最小频率的字符分配给 z 的左侧，并将频率排在第二位的分配给 z 的右侧，然后将 z 赋值为两个字符频率的和，z的权值是他们孩子中字典序最小的字母的ASCII码值；然后从队列 Q 中删除 B 和 D，并将它们的和添加到队列中
• （2）紧接着，重新创建一个空的节点 z，并将 4 作为左侧的节点，频率为 5 的 A 作为右侧的节点，4 与 5 的和作为父节点，z的权值是孩子中字典序最小的字母的ASCII码值，并把这个和按序加入到队列中，再根据频率从小到大构建树结构（小的在左，相同时，把节点z看作是字符的ASCII码值为0，权值较小的在左）。
• （3）继续按照之前的思路构建树，直到所有的字符都出现在树的节点中，哈弗曼树构建完成。

4. 对字符进行编码： 哈夫曼树构建完成，下面我们要对各个字母进行编码，编码原则是：对于每个非叶子节点，将 0 分配给连接线的左侧，1 分配给连接线的右侧，最终得到字符的编码就是从根节点开始，到该节点的路径上的 0 1 序列组合。 最终各字符的编码如下： 因此各个字母的编码分别为：

题目描述

给定一个字符串，按以上的方式求出每个字符的哈夫曼编码。

格式

输入

一个由大写字母组成的字符串，长度不超过 1000。

输出

按字典序排列的若干行，每行的格式为： 字母:该字母的哈夫曼编码。

样例

BCAADDDCCACACAC

A:11
B:100
C:0
D:101

测试限制

每个测试点均为 1s, 1024KiB .