#P18406. Sequence Shift

Sequence Shift

Sequence Shift

给定两个长度均为 nn 的整数序列 a=[a1,…,an]a=[a_1,\ldots,a_n] 和 b=[b1,…,bn]b=[b_1,\ldots,b_n],定义

f(a,b)=max⁡1≤i≤n(ai+bi).f(a,b)=\max_{1\le i\le n}(a_i+b_i).

你需要依次执行 qq 次操作。每次操作先把 bb 向左移动一位,丢弃原来的第一个元素,再把给定整数 vv 加到末尾。因此,操作后的序列为

[b2,b3,…,bn,v].[b_2,b_3,\ldots,b_n,v].

aa 始终不变。请输出操作开始前以及每次操作完成后的 f(a,b)f(a,b)。

输入格式

第一行包含两个整数 n,qn,q,其中 1≤n≤1061\le n\le10^6,0≤q≤1060\le q\le10^6。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

第三行包含 nn 个整数 b1,…,bnb_1,\ldots,b_n,表示初始序列 bb。

接下来 qq 行,每行包含一个整数,表示本次追加值的加密形式。设输入的这个整数为 xx,上一次输出的答案为 lastlast,则本次真正追加的值为

v=x⊕last,v=x\mathbin{\oplus}last,

其中 ⊕\oplus 表示按位异或。第一次操作使用的 lastlast 是初始的 f(a,b)f(a,b);此后使用上一次操作后的答案。每次追加后都要重新计算并输出答案。

随机保证:所有 aia_i、初始的 bib_i 以及每次操作真正追加的 vv,均从 [1,109][1,10^9] 中的整数均匀随机选取。 原样例不受这个随机保证约束,但程序仍须正确处理原样例。

上述数值范围针对的是解密后的值;输入中的加密整数不受 [1,109][1,10^9] 限制。

输出格式

输出 q+1q+1 行,每行一个整数。第一行是初始的 f(a,b)f(a,b),第 kk 行(2≤k≤q+12\le k\le q+1)是执行前 k−1k-1 次操作后的 f(a,b)f(a,b)。即使 q=0q=0,也要输出初始答案。

样例

5 3
1 4 3 2 5
7 5 8 3 2
3
6
4
11
13
16
25

帮助理解:三个实际追加值依次为 3⊕11=83\oplus11=8、6⊕13=116\oplus13=11、4⊕16=204\oplus16=20。初始答案为 1111,三次操作后的答案依次为 13,16,2513,16,25。