题目描述

输入n（2<n<20）个非空字符和字符的出现频率（这些信息已经按频率的升序排好）。 1、根据输入的字符和频率构建哈夫曼树，约定两个权值最小的结点其中最小的作为新结点的左子结点，次小的作为右子结点。 2、通过哈夫曼树生成哈夫曼编码：约定左分支上的编码为“0”，右分支上的编码为“1”。 从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码。 请输出这些字符的哈夫曼编码(按编码长度从短到长排列)。

输入格式

多行。第1行一个整数n。后面n行，每行是一个字符和字符的频率。

输出格式

n行，每行是一个字符和这个字符的哈夫曼编码，输出顺序按编码长度从短到长排列。

样例

输入样例 1

4
B 1
D 3
A 5
C 6

输出样例 1

C 0
A 11
B 100
D 101

输入样例 2

2
X 1
Y 2

输出样例 2

X 0
Y 1

输入样例 3

4
W 1
X 1
Y 1
Z 1

输出样例 3

W 00
X 01
Y 10
Z 11

输入样例 4

5
E 1
D 2
C 4
B 8
A 16

输出样例 4

A 1
B 01
C 001
D 0001
E 0000