编程题：哈夫曼编码

对于给定的文本内容，要求采用哈夫曼编码并输出编码后的内容。文本内容由英文字母构成，这里约定不区分字母的大小写。注意，这里约定构造哈夫曼树时，任一结点的左孩子权值不大于右孩子权值，哈夫曼编码时，左分支写'0'右分支写'1'；若两个字母的权值相等，则字典序小的字母优先；对于相等的权值，按出现的先后顺序处理。

例如，对于样例1，因不区分大小写，若按大写字母处理，则字母A、B、C、D的出现次数为4、1、2、1，则B对应的1为左孩子，D对应的1为右孩子，得到的父结点权值为2，比原有的2晚出现，因此原来的2为左孩子，新得到的2作为右孩子，对于两个权值4也类似处理。构造所得的哈夫曼树如下图所示。



### 输入格式:

测试数据有多组，处理到文件尾。每组测试数据在一行上输入一个字符串（仅由大小写英文字母构成且长度不超过360，至少包含2种字母）表示文本内容。

### 输出格式:

对于每组测试数据，输出哈夫曼编码后的内容。

### 输入样例:

in
AcBDaCAA
eAbCDaAAA


### 输出样例:

out
01011011101000
01110000010101111


### 来源:
黄龙军, 等. 数据结构与算法（Python语言描述）,上海: 上海交通大学出版社, 2023. （In Press）





答案：若无答案欢迎评论