小a和小b会使用 n 种不同的字符写小纸条。由于在传递的过程中有人会偷看，所以他们决定对所有的字符进行编码。编码只由 0,1 两个数字组成。

根据过往的小纸条，小a和小b算出了他们使用这 n 种不同的字符的概率。鉴于有的同学可能还没学过什么叫概率，那么这里我们用一种更通俗的方式讲，这 nn 种字符的使用频率的比例为 a[1]:a[2]:……:a[n] 由于他们不想让一个串编码可能解密出多种不同的原码，所以这 n 种不同的字符对应的编码都不能是其他 n−1 种字符的编码的前缀。

现在他们想知道，怎样编码才能满足上述要求，并且使得以后他们对他们的小纸条编码时，平均码长能达到最短？

输入格式 第一行有一个整数 n。

第二行有 n 个整数，其中第 i 个数为 a_i，且保证比第 i−1 个叶子结点的权值大。

保证 n≤1000，且每个叶子结点的权值 ≤10000。

输出格式 每一行为一个字符串，表示第 i 种字符对应的哈夫曼编码。 样例输入：

5

1 2 3 4 5

输出

000

001

01

10

11