暂无测试数据。

题目描述

有一条公路，上面依次排列着 $n$ 个村庄 $1,2,\cdots n$。

现在村民想要从一个村庄开始开车旅行。

人们对新的景物总是会感到好奇，所以村民第一次经过村庄$i,(1\leq i\leq n)$ 时会获得 $v_{i}$ 的幸福度。

太长的路途会让人觉得无聊，所以村民每一次经过村庄 $i,(1\leq i\leq n)$ 上时会损失 $l_{i}$ 的幸福度。

现在每个村庄的村民都想进行一次开车旅行，请问对于每个村庄 $i$ 来说，从 $i$ 出发开车旅行，可以在任意村庄结束旅行，能够获得的最大幸福度是多少。注意，刚开始从 $i$ 出发时在 $i$ 处算经过，也可以不走任何村庄直接在 $i$ 处停止。

假如从 $i$ 开始旅行的最优答案是 $a_i$，你仅需要输出所有 $(a_i+10^9)$ 的按位异或和。

输入格式

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

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

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

输出格式

一行，$1$ 个数，表示所有 $(a_i+10^9)$ 的按位异或和。

数据范围

测试点	$n \leq$	特殊性质
$1$	$10$	无
$2$	$50$	无
$3$	$300$	无
$4\sim 5$	$5000$	无
$6$	$10^6$	A
$7$	$10^6$	B
$8\sim 10$	$10^6$	无

特殊性质 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$。

5
5 2 0 1 9 
1 0 9 4 0 

999999986

20
403061601 810591352 507697501 133858564 199789041 557025869 711882319 419096063 981339518 841485142 791291503 6826013 647433775 746040274 424106727 193672792 49267733 897961281 85565522 677623767 
478730989 57478801 50960041 853526974 597724824 966224864 425308897 126068196 599927460 506175250 1836895 437092799 846100975 327742642 946884910 842167722 756988466 714029261 13657019 333939215 

1154044335