K. Sequence Shift
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

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.

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