题目描述

如果事先知道字母中被压缩的文本出现的相对频率，那么Huffman（哈夫曼）编码是一种最优的数据压缩方法。这一方法首先构建Huffman树如下：从若干棵树组成的森林开始，每一棵树是一个单一的节点，包含了文本中的一个字符及其频率（字符值仅在最终构成的树的叶节点中）；构造算法的每一步都是提取两棵具有最低频率值的树（如果频率值相同则任意选择），添加一个新的树根节点，把原来的两棵树作为新节点的左子树（频率较小）和右子树（频率较大）；新节点的频率值是两棵子树的频率值之和。这一过程重复执行，直到只剩一棵树。此过程的一个例子如下图所示，假设我们有一个文件，只包含5个字符——A、B、C、D和E，它们的频率分别是10%，14%，31%，25%和20%。 在构建了一棵哈夫曼树之后，按如下所述给每个字符分配哈夫曼编码。

把每棵树械分支标记为0，右分支标记为1.从根节点到一个字符节点，整个路径上的标号就是那个字符的哈夫曼编码。如上图所示的哈夫曼树的编码结果如下：A-010，B-011，C-11，D-10，E-00。

请编写一个程序，给定任何一个字符串，输出该字符串的哈夫曼编码。

格式

输入

一个字符串，该字符串由至少两个不同的字符组成。

输出

一个字符串，为原字符串的哈夫曼编码。

例子

bab

101

ccccbba

1111010100