Uukjeo

Interview

Time limit1sMemory limit512 MB

Summary

Given N word lengths, build binary words of those lengths where no word is a prefix of another, or report -1 if it is impossible.

Level: Medium5 of 10
Topics: Greedy, Sorting, String
Solved: No attempts yet

Problem

Uukjeo is the language that Uk-je uses, and it uses only the characters 0 and 1. Uukjeo has $N$ words, and the length of each word is $L_1, L_2, \ldots, L_N$ . Uukjeo speakers often understand each other without saying a word to the end, because no word is a prefix of another word.

Jun-o, a Dongtan resident who wanted to learn Uukjeo, secretly obtained information about it. He got only the word lengths, not the words themselves. Given the N word lengths $L_1, L_2, \ldots, L_N$ , determine whether words can be made so that no word is a prefix of another word.

Input

The first line contains the number of words $N$ ( $1 \le N \le 1{,}000$ ). The second line contains $L_1, L_2, \ldots, L_N$ . The sum of the word lengths is a natural number at most 1,000.

Output

If it is possible to make $N$ Uukjeo words, print 1 on the first line. From the second line on, print the $N$ Uukjeo words, one per line. The words must follow the input order: a word of length $L_1$ , a word of length $L_2$ , ..., and a word of length $L_N$ .

If it is impossible to make $N$ Uukjeo words, print -1.

Examples2

Example 1
Input
```
3
1 2 3
```
Expected output
```
1
0
10
110
```
Example 2
Input
```
3
1 1 1
```
Expected output
```
-1
```