哈夫曼编码与译码

Description:

已知电文包括的字符集为{A，C，I，M，N，P，T，U}，输入对应权值，对字符集合进行哈夫曼编码，完成电文的哈夫曼编码与译码工作。

Input:

共三行：

第一行为对应字符集{A，C，I，M，N，P，T，U}的权值

第二行为一段字符串表示的电文(长度不超过1000）；

第三行为一段电文的哈夫曼编码。

Output:

共十行：

前八行为各字符的编码；

第九行是与第二行输入对应的哈夫曼编码；

第十行是与第三行输入对应的电文。

Sample Input:

1 2 3 4 5 6 7 8
NUPTICPCACM
1111011111100

Sample Output:

A: 11110
C: 11111
I: 1110
M: 100
N: 101
P: 110
T: 00
U: 01
1010111000111011111110111111111011111100
ACM

Note:

2012.4.11 更新

本题由旧版NOJ导入，来源：NUPT ACM