题目描述

徐老师之前玩过一款名为《单人成行》的探索游戏，但是之前由于游戏难度太高，他一直没有通关

这天他看到了消息，说游戏降低了难度！

在这个游戏的关卡中有 $n$ 个房间，编号依次为 $1 \sim n$，相邻编号的房间是连在一起的，徐老师不能跨过相邻的房间到达其他房间

例如想要从 $5$ 号房间到达 $7$ 号房间，必须穿过 $6$ 号房间

其中对于每个房间：

1. 每个房间内有一个一次性道具，第一次进入房间时徐老师会获得这个道具，并回复 $a_i$ 点血量，之后重复进入该房间不会重复回复血量
2. 每个房间存在陷阱机关，每次进入该房间一定会触发陷阱，扣除 $b_i$ 点血量（每次进入该房间都会触发陷阱）

游戏开始时，徐老师会随机出生在一个房间（此时徐老师会立刻获得该房间的道具，并且触发该房间的陷阱），然后徐老师可以任意规划移动方案，也可以在任意时刻任意房间结束游戏，游戏的任务是使得最终血量尽可能高

现在徐老师想知道，他出生在每一个房间的最终答案是多少，用 $ans_i$ 表示他出生在 $i$ 号房间时，最终能获得的最高血量

P.S. 由于游戏降低了难度，所以在游戏过程中，徐老师的血量可以为负，此时徐老师仍然可以继续游戏，并且最终血量也有可能为负

输入格式

输入第一行包含一个整数 $n$ 表示房间数量

输入第二行包含 $n$ 个非负整数 $a_i$ 含义如题

输入第三行包含 $n$ 个非负整数 $b_i$ 含义如题

输出格式

由于需要输出的答案过多，所以请将所有 $ans_i$ 加上 $1e9$ 后的结果按位异或的结果输出

数据范围

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

特殊性质 $A$：对于所有的 $i$ 满足 $2 * b_i \leq a_i$。

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

对于 $100$ 的数据满足 $1\leq n\leq 10^6,0 \leq a_i,b_i \leq 10^9$。

样例输入1

5
5 2 0 1 9 
1 0 9 4 0

样例输出1

999999986

样例解释1

出生在 $1$ 号房间时，最优方案是向右到 $2$ 号房间然后停止，此时血量最大，为 $5-1+2-0=6$

出生在 $2$ 号房间时，最优方案是向左到 $1$ 号房间然后停止，此时血量最大，为 $2-0+5-1=6$

出生在 $3$ 号房间时，最优方案是向左到 $1$ 号房间停止或者向右到 $5$号房间停止，此时血量最大，为 $0-9+2-0+5-1=-3$ 或者 $0-9+1-4+9-0=-3$

出生在 $4$ 号房间时，最优方案是向右到 $5$ 号房间停止，此时血量最大，为 $1-4+9-0=6$

出生在 $5$ 号房间时，最优方案是不移动直接停止，此时血量最大，为 $9-0=9$

所以最终的 $ans$ 分别为 $6,6,-3,6,9$

加上 $10^9$ 后的异或和为 $999999986$。

样例输入2

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

样例输出2

1154044335