XOR-Gun

YouKnowWho Replay of National Girls'...
Limits 2s, 256 MB

YouKn0wWho has an integer sequence a1,a2,,ana_1, a_2, \ldots, a_n. He will perform the following operation until the sequence becomes empty: Select a non-empty subsequence of aa such that the bitwise XOR of the elements of the subsequence is xx, 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 qq queries each containing an integer xx. Solve the problem independently for each xx.

Input

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

The second line contains nn space-separated integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai<2300 \le a_i \lt 2^{30}).

Each of the following qq lines contains an integer xx (0x<2300 \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][1, 3, 5] as 135=71 \oplus 3 \oplus 5 = 7. So the modified sequence will be a=[2,5]a=[2, 5]. Now erase the whole sequence as 25=72 \oplus 5 = 7. It can be shown that it is not possible erase the whole sequence using less than 22 operations.

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

Submit

Login to submit.

Statistics

75% Solution Ratio
NirjhorEarliest, 8M ago
LUMBERJACK_MANFastest, 0.1s
prodip_bsmrstuLightest, 1.0 MB
serotoninShortest, 571B
Toph uses cookies. By continuing you agree to our Cookie Policy.