20453번 - Сложение без переносов 서브태스크다국어

Операция побитового <<или>> для набора целых положительных чисел, записанных в двоичной системе счисления, устроена следующим образом. Результатом её применения является число, в двоичной записи которого единица устанавливается в тех разрядах, в которых содержится единица хотя бы у одного числа из набора.

В редких случаях побитовое <<или>> можно использовать для сложения целых положительных чисел, записанных в двоичной системе счисления. Сумма набора чисел равна их побитовому <<или>>, если для каждого разряда имеется не более одного числа из этого набора, у которого в этом разряде находится единица. Такие наборы чисел назовём красивыми.

Задан набор целых положительных чисел $a_1, a_2, \ldots, a_n$. Необходимо построить красивый набор целых положительных чисел $b_1, b_2, \ldots, b_n$, чтобы для всех $i$ от $1$ до $n$ выполнялось условие $b_i \ge a_i$, а сумма $b_1+b_2+\ldots+b_n$ была минимальна.

Требуется написать программу, которая по двоичной записи чисел $a_1, a_2, \ldots, a_n$ определяет двоичную запись минимального значения суммы искомого красивого набора $b_1, b_2, \ldots, b_n$.

В первой строке записано целое число $n$ --- количество чисел в наборе ($2 \leq n \leq 300\,000$).

Следующие $n$ строк содержат двоичную запись целых положительных чисел $a_i$, по одному в строке. Числа не содержат ведущих нулей, и суммарная длина их двоичных записей не превосходит~$300\,000$.

Требуется вывести двоичную запись минимальной суммы искомого красивого набора $b_1, b_2, \ldots, b_n$. Ответ необходимо вывести без ведущих нулей.