Taman is excited to announce that he has learnt bitwise AND operation. His Big Sister Titly
has given him a sequence of non-negative integers
x1, x2,..., xn as key. To test that whether
Taman knows bitwise AND operation or not, Taman is asked to find maximum value among
all (
a AND xi) where
1
i
N. But their youngest sister Tamanna is not happy with this. She
adds another condition that for a given sequence, Taman has to answer Q queries instead of
just one. Can you help poor Taman?
Note:
Expression
x AND y means applying the operation of bitwise AND to numbers x and y. This
operation exists in all modern programming languages, for example, in language C++ and
Java it is marked as "&".
First line of input will contain the number of test cases, T
5. Then T test cases follow.
First line of each test case contains two integers N (
1
N
100000) and Q (
1
Q
30000)
separated by a single space. Next line contains N integers
x1, x2,..., xn separated by a single
space (
0
xi < 109). Each of next Q lines describes a query which consists of a single integer
a (
0
a < 230).
For each query output a single integer, the maximum value of (
a AND xi) where
1
i
N.
1
3 3
1 2 3
10
11
12
2
3
0
Problem Setter: Muhammed Hedayet
Alternate Solution: Kazi Rakibul Hossain