Practice on Toph

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

The Perfect Collection

By Labib666 · Limits 1s, 512 MB

Given an array A of N integers, if we choose any K of these integers and calculate their bitwise XOR, what is the minimum possible result that we can get?

A bitwise XOR takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same. For more detail, visit Wikipedia

Input

The first line of the input contains two integers, N (1 ≤ N ≤ 102) and Q (1 ≤ Q ≤ 103), the size of the given array and the number of queries .

The next line contains N space separated integers, the elements of the array A (1 ≤ Ai ≤ 103).

The next Q lines contain one integer each. ith of these integers represents the value of K (1 ≤ K ≤ N) for the ith query.

Output

For each query, print one integer in a separate line: the minimum possible bitwise XOR value of any K integers of the given array.

Sample

InputOutput
4 2
2 5 7 4
2
1
1
2

Explanation

For the first query, the possible choices here are: (2,5), (2,7,), (2,4), (5,7), (5,4), (7,4).
Among these, the bitwise XOR of (5,4) yields 1 which is the minimum of all the six possible results.

For the second query, 2 is minimum value in the given array.

Discussion

Statistics


61% Solution Ratio

exsurrealEarliest, Oct '16

farhanhasinFastest, 0.0s

exsurrealLightest, 393 kB

rathijitpaponShortest, 435B

Submit

Login to submit

Editorial

This is a dynamic programming problem with three state parameters: your current position in the arra...

Toph uses cookies. By continuing you agree to our Cookie Policy.