4832 - 字符的频率

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

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个字母

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题