序列位移 - 题目

给定两个长度为 $n$ 的序列：$[a_1, a_2, \dots, a_n]$ 和 $[b_1, b_2, \dots, b_n]$。$f(a, b)$ 的值定义为 $f(a, b) = \max \{a_i + b_i\}$，其中 $1 \le i \le n$。

序列 $b$ 可以进行移动。你将进行 $q$ 次操作，每次操作分为以下两个步骤：

首先，将序列 $b$ 向左移动一位，并丢弃第一个元素，使得序列 $b'$ 变为 $[b'_1 = b_2, b'_2 = b_3, \dots, b'_{n-1} = b_n]$。
然后，将 $v$ 追加到 $b$ 的最右侧，使得序列 $b'$ 变为 $[b'_1 = b_2, b'_2 = b_3, \dots, b'_{n-1} = b_n, b'_n = v]$。

在本题中，你的任务是求出每次操作前后 $f(a, b)$ 的值。

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 1\,000\,000, 0 \le q \le 1\,000\,000$)，分别表示序列的长度和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $a$。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示初始序列 $b$。

接下来的 $q$ 行，每行包含一个整数 $v$，表示每次操作中追加的值。该值 $v$ 经过加密以强制要求在线处理。

保证所有 $a_i, b_i$ 和 $v$ 的值均从 $[1, 10^9]$ 的整数中均匀随机选取。随机性条件不适用于样例测试，但你的程序必须能够通过样例测试。

设 $last$ 为你上一次回答的 $f(a, b)$ 的值。对于每次操作，实际的 $v$ 值为 $v \oplus last$。在上述表达式中，符号“$\oplus$”表示按位异或运算。同时请注意，题目中描述的约束条件仅在解密后适用于相应的参数，加密后的值不受这些约束限制。

输出 $q + 1$ 行。

第一行输出一个整数，表示初始的 $f(a, b)$ 值。

在第 $k$ 行（$2 \le k \le q + 1$），输出一个整数，表示第 $(k-1)$ 次操作后当前的 $f(a, b)$ 值。

QOJ.ac