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 2 1
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
This is a dynamic programming problem with three state parameters: your current position in the arra...