# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# XOR-Gun

By YouKnowWho · Limits 2s, 256 MB

YouKn0wWho has an integer sequence $a_1, a_2, \ldots, a_n$. He will perform the following operation until the sequence becomes empty: Select a non-empty subsequence of $a$ such that the bitwise XOR of the elements of the subsequence is $x$, and then erase the elements of that subsequence.

He is wondering if it is possible to erase the whole sequence by performing the operation as many times as he wants. If possible, then he wants to find the minimum number of operations that he has to perform to erase the whole sequence. Help YouKn0wWho solve the problem as he is busy preparing a contest.

You will be given $q$ queries each containing an integer $x$. Solve the problem independently for each $x$.

## Input

The first line contains two space-separated integers $n$ and $q$ ($1 \le n, q \le 3 \cdot 10^5$).

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt 2^{30}$).

Each of the following $q$ lines contains an integer $x$ ($0 \le x \lt 2^{30}$).

## Output

For each query -

• Print -1, if it is not possible to erase the whole sequence by performing the aforementioned operation one or more times.

• Otherwise, output the minimum number of operations that YouKn0wWho has to perform to erase the whole sequence.

## Sample

InputOutput
5 5
1 3 2 5 5
7
10
3
0
8

2
-1
2
1
-1


In the first query, in the first operation erase the subsequence $[1, 3, 5]$ as $1 \oplus 3 \oplus 5 = 7$. So the modified sequence will be $a=[2, 5]$. Now erase the whole sequence as $2 \oplus 5 = 7$. It can be shown that it is not possible erase the whole sequence using less than $2$ operations.

In the second query, it is not possible to erase the whole sequence.

### Statistics

75% Solution Ratio

NirjhorEarliest, 1M ago

LUMBERJACK_MANFastest, 0.1s

prodip_bsmrstuLightest, 1.0 MB

serotoninShortest, 571B