Problem D: 构建哈夫曼树并输出编码

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：24 Solved：8

Description

给定 n 个字符及其出现频率，构建哈夫曼树，并输出每个字符的哈夫曼编码。

要求：左子树编码为 '0'，右子树编码为 '1'；当两个节点权值相同时，先输入的优先合并。



Input

第一行一个整数 n（2 ≤ n ≤ 26）。

接下来 n 行，每行一个字符 c 和一个整数 f，表示字符和频率。

Output

按输入顺序，每行输出"字符 编码"。

Sample Input Copy 

5
A 5
B 2
C 1
D 1
E 2

Sample Output Copy 

A 0
B 110
C 1110
D 1111
E 10

HINT

2 ≤ n ≤ 26