Sequence Shift
Description
You are given two sequences of length $n$: $[a_1,a_2,\dots,a_n]$ and $[b_1,b_2,\dots,b_n]$. The value of $f(a,b)$ is defined as $f(a,b)=\max\left\{a_i+b_i\right\}$, where $1\leq i\leq n$.
The sequence $b$ can be shifted. You will then be given $q$ operations, each operation can be divided into the following two steps:
- First, shift the sequence $b$ to the left by one position, and drop the first element, so the sequence $b'$ will be $[b'_1=b_2$, $b'_2=b_3$, $\dots$, $b'_{n-1}=b_n]$.
- Then, append $v$ to the rightmost place of $b$, so the sequence $b'$ will be $[b'_1=b_2$, $b'_2=b_3$, $\dots$, $b'_{n-1}=b_n$, $b'_n=v]$.
In this problem, your task is to figure out the value of $f(a,b)$ before/after each operation.
The first line of the input contains two integers $n$ and $q$ ($1 \leq n \leq 1\,000\,000$, $0\leq q\leq 1\,000\,000$), denoting the length of the sequences and the number of operations.
The second line contains $n$ integers $a_1,a_2,\dots,a_n$, denoting the sequence $a$.
The third line contains $n$ integers $b_1,b_2,\dots,b_n$, denoting the initial sequence $b$.
Each of the next $q$ lines contains a single integer $v$, denoting the value that will be appended in each operation. The value of $v$ will be encrypted in order to enforce online processing.
It is guaranteed that all the values of $a_i,b_i$ and $v$ are chosen uniformly at random from integers in the range $[1, 10^9]$. The randomness condition does not apply to the sample test(s), but your solution must pass the sample test(s) as well.
Let $last$ be the previous value of $f(a,b)$ that you answered. For each operation, the actual value of $v$ is $v \oplus last$. In the expressions above, the symbol "$\oplus$" denotes the bitwise exclusive-or operation. Also, note that the constraints described in the statement above apply to the corresponding parameters only after decryption, the encrypted values are not subject to those constraints.
Print $q+1$ lines.
Output a single integer in the first line, denoting the initial value of $f(a,b)$.
In the $k$-th line $(2\leq k\leq q+1)$, output a single integer denoting the current value of $f(a,b)$ after the $(k-1)$-th operation.
Input
The first line of the input contains two integers $n$ and $q$ ($1 \leq n \leq 1\,000\,000$, $0\leq q\leq 1\,000\,000$), denoting the length of the sequences and the number of operations.
The second line contains $n$ integers $a_1,a_2,\dots,a_n$, denoting the sequence $a$.
The third line contains $n$ integers $b_1,b_2,\dots,b_n$, denoting the initial sequence $b$.
Each of the next $q$ lines contains a single integer $v$, denoting the value that will be appended in each operation. The value of $v$ will be encrypted in order to enforce online processing.
It is guaranteed that all the values of $a_i,b_i$ and $v$ are chosen uniformly at random from integers in the range $[1, 10^9]$. The randomness condition does not apply to the sample test(s), but your solution must pass the sample test(s) as well.
Let $last$ be the previous value of $f(a,b)$ that you answered. For each operation, the actual value of $v$ is $v \oplus last$. In the expressions above, the symbol "$\oplus$" denotes the bitwise exclusive-or operation. Also, note that the constraints described in the statement above apply to the corresponding parameters only after decryption, the encrypted values are not subject to those constraints.
Output
Print $q+1$ lines.
Output a single integer in the first line, denoting the initial value of $f(a,b)$.
In the $k$-th line $(2\leq k\leq q+1)$, output a single integer denoting the current value of $f(a,b)$ after the $(k-1)$-th operation.
5 3
1 4 3 2 5
7 5 8 3 2
3
6
4
11
13
16
25