题目描述

赫夫编码，是一种即使可译编码，即计算出每个字符出现的概率，从小到大、从下至上的排序后，把下面的两个字符用[连接，组成一个整体，再把这个整体与上面的字符用[连接。重复这个操作，让整个数列变成一棵向左旋转 $90\degree$ 的二叉树。把手上画好的草图的每个[的上方的直角标记 $0$ ，下方的直角标记 $1$ 。最后到某个字符的唯一路径就是该字符的赫夫编码。

输入格式

共 $N+1$ 行。

第一行一个整数 $N$，表示字符个数。

接下来 $N$ 行，每行一个百分数（如：$10.5\%,60\%$），表示第 $i$ 个字符出现的概率。

输出格式

共 $N$ 行，每行一个二进制数，表示第 $i$ 个字符的赫夫编码。

样例

4
12.5%
50%
12.5%
25%

110
0
111
10

3
11.45%
19.19%
69.36%

00
01
1

说明/提示

【提示】

第一个样例的输入不符合该题的规定，因此它不能成为评判代码正确性的标准。

【数据范围】

对于 $100\%$ 的数据，满足 $1\le n\le 100$，所有概率不相等且加和为 $100\%$。

【提示】

悄悄告诉你一个秘密：c++的sort函数会超时！