Sequence Shift
给定两个长度均为 n 的整数序列 a=[a1,…,an] 和 b=[b1,…,bn],定义
f(a,b)=1≤i≤nmax(ai+bi).
你需要依次执行 q 次操作。每次操作先把 b 向左移动一位,丢弃原来的第一个元素,再把给定整数 v 加到末尾。因此,操作后的序列为
[b2,b3,…,bn,v].
a 始终不变。请输出操作开始前以及每次操作完成后的 f(a,b)。
输入格式
第一行包含两个整数 n,q,其中 1≤n≤106,0≤q≤106。
第二行包含 n 个整数 a1,…,an。
第三行包含 n 个整数 b1,…,bn,表示初始序列 b。
接下来 q 行,每行包含一个整数,表示本次追加值的加密形式。设输入的这个整数为 x,上一次输出的答案为 last,则本次真正追加的值为
v=x⊕last,
其中 ⊕ 表示按位异或。第一次操作使用的 last 是初始的 f(a,b);此后使用上一次操作后的答案。每次追加后都要重新计算并输出答案。
随机保证:所有 ai、初始的 bi 以及每次操作真正追加的 v,均从 [1,109] 中的整数均匀随机选取。 原样例不受这个随机保证约束,但程序仍须正确处理原样例。
上述数值范围针对的是解密后的值;输入中的加密整数不受 [1,109] 限制。
输出格式
输出 q+1 行,每行一个整数。第一行是初始的 f(a,b),第 k 行(2≤k≤q+1)是执行前 k−1 次操作后的 f(a,b)。即使 q=0,也要输出初始答案。
样例
5 3
1 4 3 2 5
7 5 8 3 2
3
6
4
11
13
16
25
帮助理解:三个实际追加值依次为 3⊕11=8、6⊕13=11、4⊕16=20。初始答案为 11,三次操作后的答案依次为 13,16,25。