题目描述

有 $1,2,\cdots ,n$ 个景点依次排列。现在小 L 想要从一个景点开始旅游，每次可以从一个景点走到它相邻的一个景点。小 L 第一次经过第 $i$ 个景点会获得 $v_i$ 的开心值，但是每经过一次第 $i$ 个景点会损失 $l_i$ 的开心值。

他想知道对于每个景点 $i$ 来说，从 $i$ 出发旅游，可以在任意景点结束旅游，能够获得的最大开心值是多少。注意，刚开始从 $i$ 出发时在 $i$ 处算经过，也可以不走任何景点直接在 $i$ 处停止。

假如从 $i$ 开始旅游的最优答案是 $a_i$，你仅需要输出所有 $(a_i+10^9)$ 的按位异或和，即 $(a_1+10^9)$ $\mathrm{xor}$ $(a_2+10^9)$ $\mathrm{xor}$ $\cdots$ $\mathrm{xor}$ $(a_n+10^9)$。

输入格式

第一行，一个正整数 $n$．

第二行，$n$ 个非负整数 $v_i$．

第三行，$n$ 个非负整数 $l_i$．

输出格式

一行，$1$ 个数，表示所有 $(a_i+10^9)$ 的按位异或和，即 $(a_1+10^9)$ $\mathrm{xor}$ $(a_2+10^9)$ $\mathrm{xor}$ $\cdots$ $\mathrm{xor}$ $(a_n+10^9)$。

样例

样例输入 1

5
5 2 0 1 9 
1 0 9 4 0 

样例输出 1

999999986

样例输入 2

见下发文件。

样例输出 2

见下发文件。

大样例 点击下载

样例 1 解释

从每个位置出发旅游的最优答案分别为：

6 6 -3 6 9

数据范围

特殊性质 A：对于所有的 $i$ 满足 $2l_i\leq v_i$．

特殊性质 B：对于所有的 $i$ 满足 $v_i,l_i$ 在 $[0,10^9]$ 内随机生成．

对于 $100\%$ 的数据：$1\leq n\leq 10^{6},0\leq v_i,l_i\leq 10^9$．