Beautiful Set

Given a sequence of natural numbers (a_1, a_2, \dots, a_n) (each given in binary notation), we want to find a sequence (b_1, b_2, \dots, b_n) (which will also be output in binary) satisfying the following conditions:

1. For every (i=1,2,\dots,n), (b_i \ge a_i) (comparison in the usual integer sense).
2. The set ({b_1,b_2,\dots,b_n}\n) is called beautiful if [ \sum_{i=1}^n b_i ;=; b_1; \mathtt{OR} ; b_2 ;\mathtt{OR}; \cdots ;\mathtt{OR}; b_n ;. ] In other words, when writing each (b_i) in binary, no binary digit (power of 2) is used in more than one (b_i) (so that the sum equals the bitwise OR).

Among all beautiful sequences (b_i) satisfying (b_i\ge a_i) for all (i), find one with the minimum possible (\sum_{i=1}^n b_i) and output this sum in binary notation.

Explanation

Since a beautiful set requires that the binary representations of the \(b_i\)’s have no overlapping 1’s, the total sum is simply the bitwise OR of all \(b_i\)’s. In order to keep the total sum as low as possible while ensuring that each \(b_i\ge a_i\), we are allowed to increase some \(a_i\) slightly. For example, if two elements force the same bit to be 1 (causing a conflict), one may be "bumped" to a higher number so that its binary expansion uses a different (and higher) power of 2, resolving the conflict.

A greedy repair algorithm can be used: start with \(b_i = a_i\) (interpreting the binary strings as integers). While there is a conflict – meaning there exist two indices \(i\neq j\) with \(b_i \land b_j \ne 0\) – choose one of the conflicting numbers and increase (or "bump") it to the smallest number (of the form either a power of 2 or a number equal to such a power of 2) that is greater than its current value. (Note that if \(x\) is not itself a power of 2 then the next number is \(2^{\lfloor\log_2(x)\rfloor+1}\); if \(x\) is a power of 2 the next candidate is \(2x\).) This procedure guarantees that eventually all conflicts are resolved and the resulting set is beautiful. It can be shown that this greedy method produces an optimal (i.e. minimum sum) solution.

Input and output note:
All numbers (both input and output) are given as binary strings (with no leading zero unless the number is 0).

inputFormat

The first line contains a single integer \(n\) (the number of elements).
The following \(n\) lines each contain a binary string representing the number \(a_i\) (with no leading zero unless the number is 0).

outputFormat

Output a single binary string – the minimal possible value of \(\sum_{i=1}^n b_i\) for some beautiful set satisfying \(b_i \ge a_i\) for all \(i\).

sample

2
1
1

11