Addition Without Carries

Time limit2sMemory limit512 MB

Summary

Given n binary numbers, choose b_i at least a_i so that no two b_i share a 1 bit, minimizing the sum, and print that sum in binary.

Level: Hard9 of 10
Topics: Greedy, Bit manipulation
Solved: No attempts yet

Statement

In rare cases, bitwise OR can replace addition of positive integers written in binary. The sum of a set equals its bitwise OR when every bit position has at most one number in the set with a 1 in that position. Call such a set beautiful.

Bitwise OR works like this. The result has a 1 in each bit position where at least one number in the set has a 1.

You are given positive integers $a_1, a_2, \ldots, a_n$ . Build a beautiful set of positive integers $b_1, b_2, \ldots, b_n$ such that $b_i \ge a_i$ for every $i$ from 1 to $n$ , and the sum $b_1+b_2+\ldots+b_n$ is as small as possible.

Write a program that reads the binary representations of $a_1, \ldots, a_n$ and prints the binary representation of the minimal possible sum of such a beautiful set.

Input

The first line contains the integer $n$ , the number of integers in the set ( $2 \le n \le 300000$ ). Each of the next $n$ lines contains the binary representation of one positive integer $a_i$ . The numbers have no leading zeros, and the total length of their binary representations does not exceed 300000.

Output

Print the binary representation of the minimal sum of a beautiful set $b_1, b_2, \ldots, b_n$ . Print it without leading zeros.

Examples3

Example 1
Input
```
2
10
10
```
Expected output
```
110
```
Example 2
Input
```
2
10100
1001
```
Expected output
```
11101
```
Example 3
Input
```
3
1
1
110
```
Expected output
```
1011
```