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

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.

Samples

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.

Author
  • Labib666's Avatar

    Labib666

    Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms.
Discussion
Submit

Login to submit

Editorial

Login to unlock editorial