405895: GYM102154 A Addition without carry

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Addition without carrytime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 a1, a2, ..., an. You must build a beautiful set of positive integers b1, b2, ..., bn so that the condition bi ≥ ai holds true, and the sum b1 + b2 + ... + bn is minimized.

Given the binary notation of the numbers a1, a2, ..., an, find the binary notation of the minimum possible value of the sum of numbers in the desired beautiful set b1, b2, ..., bn.

Input

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 (bi).

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

Output

Print the binary notation of the minimum possible sum of numbers in the desired beautiful set b1, b2, ..., bn. Don't print leading zeros.

Scoring

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

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.

ExamplesInput
2
10
10
Output
110
Input
2
10100
1001
Output
11101
Input
3
1
1
110
Output
1011

加入题单

上一题 下一题 算法标签: