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


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.


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


4 2
2 5 7 4


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.


Login to submit.


67% Solution Ratio
exsurrealEarliest, Oct '16
Kuddus.6068Fastest, 0.0s
exsurrealLightest, 393 kB
monna4335Shortest, 383B
Toph uses cookies. By continuing you agree to our Cookie Policy.