[AdditionalFile2850.zip](file://AdditionalFile2850.zip?type=additional_file)

#2850. 「ROI 2018 Day 2」无进位加法

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

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

对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\mathtt{OR}$ 和，那么我们称之为「美丽的集合」。

给出 $a_1\ldots a_n,$ 存在一个由数列 $b_1\ldots b_n$ 组成的「美丽的集合」，且满足：

• $\forall i=1\ldots n,$ $b_i\geq a_i,$ 且
• $\sum b_i$ 最小。

试求出新数列的 $\sum b_i$。

为了简便起见，我们给出的 $a_i$ 均为二进制形式，你的答案也应是二进制形式。

样例 1

输入

2
10
10

输出

110

样例 2

输入

2
10100
1001

输出

11101

样例 3

输入

3
1
1
110

输出

1011

数据范围与提示

（在二进制下）$a_i$ 的位数不超过 $\max L$，并且所有 $a_i$ 的位数之和不超过 $3\times 10^5$。