4832 - 字符的频率

通过次数

16

提交次数

32

Time Limit : 1 秒
Memory Limit : 128 MB

根据每个字符的出现频率,构造出字符的最优二进制表示,即前缀码。

Input

在屏幕上输入字符个数和每个字符的频率。

Output

每个字符的Huffman编码。1个字母一行,每行字母后面有一个空格

Examples

Input

6
45 13 12 16 9 5

Output

a 0
b 101
c 100
d 111
e 1101
f 1100

Hint

数据范围为26个字母