CF631A.Interview

Blake is a CEO of a large company called "Blake Technologies". He loves his company very much and he thinks that his company should be the best. That is why every candidate needs to pass through the interview that consists of the following problem.

We define function f(x, l, r) as a bitwise OR of integers x__l, x__l + 1, ..., x__r, where x__i is the i-th element of the array x. You are given two arrays a and b of length n. You need to determine the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.

布莱克是名为“布莱克科技”（Blake Technologies）的一家大型公司的首席执行官。他非常热爱自己的公司，并坚信自己的公司应当做到最好。因此，每位应聘者都必须通过一场面试，而该面试包含如下问题：

我们定义函数 $ f(x, l, r) $ 为数组 $ x $ 中第 $ l $ 个元素 $ x_l $、第 $ l+1 $ 个元素 $ x_{l+1} $、……、第 $ r $ 个元素 $ x_r $ 的按位或（bitwise OR）运算结果，其中 $ x_i $ 表示数组 $ x $ 的第 $ i $ 个元素。现给定两个长度均为 $ n $ 的数组 $ a $ 和 $ b $。你需要在所有满足 $ 1 \leq l \leq r \leq n $ 的区间 $ [l, r] $ 中，找出表达式 $ f(a, l, r) + f(b, l, r) $ 的最大可能取值。

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the length of the arrays.

The second line contains n integers a__i (0 ≤ a__i ≤ 109).

The third line contains n integers b__i (0 ≤ b__i ≤ 109).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000$）—— 表示数组的长度。

第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^9$）。

第三行包含 $n$ 个整数 $b_i$（$0 \leq b_i \leq 10^9$）。

Print a single integer — the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.

输出一个整数——在所有满足 $1 \le l \le r \le n$ 的区间 $[l, r]$ 中，$f(a, l, r) + f(b, l, r)$ 的最大值。

Bitwise OR of two non-negative integers a and b is the number c = a OR b, such that each of its digits in binary notation is 1 if and only if at least one of a or b have 1 in the corresponding position in binary notation.

In the first sample, one of the optimal answers is l = 2 and r = 4, because f(a, 2, 4) + f(b, 2, 4) = (2 OR 4 OR 3) + (3 OR 3 OR 12) = 7 + 15 = 22. Other ways to get maximum value is to choose l = 1 and r = 4, l = 1 and r = 5, l = 2 and r = 4, l = 2 and r = 5, l = 3 and r = 4, or l = 3 and r = 5.

In the second sample, the maximum value is obtained for l = 1 and r = 9.

两个非负整数 $a$ 和 $b$ 的按位或（bitwise OR）结果为数 $c = a\ \text{OR}\ b$，其二进制表示中每一位均为 $1$ 当且仅当 $a$ 或 $b$ 在该二进制位上至少有一个为 $1$。

在第一个样例中，一个最优解为 $l = 2$ 且 $r = 4$，因为

$$f(a, 2, 4) + f(b, 2, 4) = (2\ \text{OR}\ 4\ \text{OR}\ 3) + (3\ \text{OR}\ 3\ \text{OR}\ 12) = 7 + 15 = 22.$$

其他可取得最大值的方案包括：$(l, r) = (1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 4)$ 或 $(3, 5)$。

在第二个样例中，最大值在 $l = 1$ 且 $r = 9$ 时取得。