Problem Description

Given a sequence of length $n$, there are $q$ queries. In each query, a positive integer $x$ is given, and the following operations are performed in order:

• XOR every number in the sequence with $x$.
• Find the longest interval $[l,r]$ ($l,r$ are non-negative integers) such that every integer in the interval appears in the sequence. The length of the interval is defined as $r-l+1$.

Note that after each query, the sequence is modified.

Some clarifications:

1. “Interval” refers to an interval of integers. For example, the integers in interval $[1,3]$ are $1,2,3$, and this is unrelated to the sequence.
2. “Sequence” refers to the modified sequence after applying the current query, and does not include any previous versions of the sequence.

Input Format

The first line contains two positive integers $n,q$, representing the sequence length and the number of queries.

The second line contains $n$ positive integers $a_i$, representing the initial sequence.

The next $q$ lines each contain one positive integer $x$, representing a query.

Output Format

Output $q$ lines, one integer per line, representing the answer to each query.

5 2
1 2 3 4 5
1
1

4
5

10 10
5 9 8 3 5 7 10 19 5 24
10
56
19
14
18
53
52
57
96
1000

2
2
2
4
2
3
3
2
2
2

Hint

Sample Explanation

For the first sample, the initial sequence is $\{1,2,3,4,5\}$. In the first query, $x=1$, so after XOR the sequence becomes $\{0,3,2,5,4\}$. Every integer $2,3,4,5$ in the interval $[2,5]$ appears in this sequence. This is the largest interval that satisfies the condition, so the answer is $5-2+1=4$.

Constraints

This problem uses bundled testdata.

For all data, it is guaranteed that $1\leq n,q,a_i,x\leq 5\times10^5$.

Translated by ChatGPT 5