Secret Sharing

Time limit2sMemory limit128 MB

Summary

Concatenate all given digit strings in the order that yields the smallest possible integer without a leading zero, or print INVALID if impossible.

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

Problem

An encryption key can be divided among several people instead of being stored as one piece. The key is split into N digit strings called shares.

A new encryption algorithm uses a very long decimal integer as its key. The key must start with a nonzero digit, and every share must be used exactly once. The order of the shares is determined by this rule: among all concatenations that use every share, the encryption key is the smallest valid decimal integer. Any concatenation that starts with 0 is invalid.

Given N shares, restore the encryption key.

Input

The first line contains the number of shares N (1 <= N <= 100).

The next line contains N digit strings. Each share has length at most 5, and a share may start with 0.

Output

Print the restored encryption key on one line.

If no key satisfies the conditions, print INVALID.

Examples4

Example 1
Input
```
5
2 4 11 33 00
```
Expected output
```
11002334
```
Example 2
Input
```
3
20 202 2020
```
Expected output
```
202020202
```
Example 3
Input
```
6
3 4 5 3 44 555
```
Expected output
```
334445555
```
Example 4
Input
```
3
0 00 007
```
Expected output
```
INVALID
```