405895: GYM102154 A Addition without carry

It's surprising but sometimes we can use the bitwise OR to add positive integers written in the binary notation. For a set of numbers, if there are no two numbers with 1 at the same position (counting positions from the right), then the sum of those numbers is equal to their bitwise OR. Such sets of numbers are called beautiful.

You are given a set of positive integers a₁, a₂, ..., a_n. You must build a beautiful set of positive integers b₁, b₂, ..., b_n so that the condition b_i ≥ a_i holds true, and the sum b₁ + b₂ + ... + b_n is minimized.

Given the binary notation of the numbers a₁, a₂, ..., a_n, find the binary notation of the minimum possible value of the sum of numbers in the desired beautiful set b₁, b₂, ..., b_n.

The first line of the input contains an integer n — the size of the given set (2 ≤ n ≤ 300 000). This is also equal to the size of the sought set (b_i).

The i-th of the next n lines contains a binary notation of a positive integer a_i. The numbers do not contain leading zeros, and the total length of their binary notations does not exceed 300 000.

Print the binary notation of the minimum possible sum of numbers in the desired beautiful set b₁, b₂, ..., b_n. Don't print leading zeros.

Let max L be the maximum length of a binary notation of a_i.

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group 0 denotes the sample test(s) from the statement.

2
10
10

110

2
10100
1001

11101

3
1
1
110

1011