P9293 [ROI 2018] Addition without carry

Translated from [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T4. [Сложение без переносов ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf) ([Addition without carry](https://codeforces.com/gym/102154/problem/A)).

For a set containing only natural numbers, if the sum of all numbers in the set equals the bitwise $\mathtt{OR}$ of all numbers in the set, then we call it a “beautiful set”. Given $a_1 \ldots a_n$, there exists a “beautiful set” consisting of the sequence $b_1 \ldots b_n$, such that: For all $i = 1 \ldots n$, $b_i \ge a_i$, and $\sum b_i$ is minimized. Find $\sum b_i$ of the new sequence. For convenience, the given $a_i$ are all in binary form, and your answer should also be in binary form.

The first line contains an integer $n$. The next $n$ lines each contain a binary number $a_i$.

Output the resulting binary value of $\sum b_i$.

For all testdata, $1 \le n \le 3 \times 10^5$. (In binary) the number of bits of $a_i$ does not exceed $3 \times 10^5$, and the sum of bit lengths of all $a_i$ does not exceed $3 \times 10^5$. The subtask dependencies are for reference only. There are no subtask dependencies in the Luogu judging. Constraints | Subtask | Score | $n$ | $\max L$ | Subtasks that must be passed | |:------:|:----:|:---:|:--------:|:----------------------------:| | 1 | 4 | $n=2$ | $\max L \le 10$ | | | 2 | 2 | $n=2$ | $\max L \le 20$ | 1 | | 3 | 2 | $n=2$ | $\max L \le 100$ | 1,2 | | 4 | 2 | $n=2$ | $\max L \le 1000$ | 1--3 | | 5 | 2 | $n=2$ | $\max L \le 300\,000$ | 1--4 | | 6 | 4 | $n \le 100$ | $\max L \le 100$ | Guaranteed that $a_i$ is a power of $2$ | | 7 | 4 | $n \le 1000$ | $\max L \le 1000$ | 6, guaranteed that $a_i$ is a power of $2$ | | 8 | 4 | $n \le 300\,000$ | $\max L \le 300\,000$ | 6,7, guaranteed that $a_i$ is a power of $2$ | | 9 | 4 | $n \le 5$ | $\max L \le 5$ | U | | 10 | 4 | $n \le 5$ | $\max L \le 1\,000$ | U,1--4,9 | | 11 | 4 | $n \le 1\,000$ | $\max L \le 5$ | U,9 | | 12 | 4 | $n \le 10$ | $\max L \le 10$ | U,1,9 | | 13 | 4 | $n \le 50$ | $\max L \le 50$ | U,1,2,9,12 | | 14 | 7 | $n \le 100$ | $\max L \le 100$ | U,1--3,6,9,12,13 | | 15 | 7 | $n \le 300$ | $\max L \le 300$ | U,1--3,6,9,12--14 | | 16 | 8 | $n \le 1000$ | $\max L \le 1000$ | U,1--4,6,7,9--15 | | 17 | 8 | $n \le 3000$ | $\max L \le 3000$ | U,1--4,6,7,9--16 | | 18 | 6 | $n \le 10\,000$ | $\max L \le 10\,000$ | U,1--4,6,7,9--17 | | 19 | 7 | $n \le 30\,000$ | $\max L \le 30\,000$ | U,1--4,6,7,9--18 | | 20 | 7 | $n \le 100\,000$ | $\max L \le 100\,000$ | U,1--4,6,7,9--19 | | 21 | 6 | $n \le 300\,000$ | $\max L \le 300\,000$ | U,1--20 | Translated by ChatGPT 5