Problem Background

Translated from ROI 2018 Day2 T4. Сложение без переносов (Addition without carry).

Problem Description

For a set containing only natural numbers, if the sum of all numbers in the set equals the bitwise OR of all numbers in the set, we call it a "beautiful set".

Given \(a_1 \ldots a_n\), there exists a "beautiful set" composed of the sequence \(b_1 \ldots b_n\), satisfying:

• \(\forall i=1 \ldots n\), \(b_i \geq a_i\), and
• \(\sum b_i\) is minimized.

Try to find the sum of the new sequence \(\sum b_i\).

For simplicity, the given \(a_i\) are in binary form, and your answer should also be in binary form.

Input Format

The first line contains an integer \(n\).

The next \(n\) lines each contain a binary number \(a_i\).

Output Format

Output the binary sum \(\sum b_i\).

Sample Input and Output

Sample Input #1

2
10
10

Sample Output #1

110

Sample Input #2

2
10100
1001

Sample Output #2

11101

Sample Input #3

3
1
1
110

Sample Output #3

1011

Notes

For all data, \(1 \leq n \leq 3 \times 10^5\).

In binary, the number of digits in \(a_i\) does not exceed \(3 \times 10^5\), and the total number of digits across all \(a_i\) does not exceed \(3 \times 10^5\).

Due to the large number of subtasks and data in the original problem, only a selection is used for evaluation here.

见题面 Input 部分

见题面 Output 部分