Practice on Toph

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

MaxXOR

By nahidhasan98 · Limits 1s, 512 MB

You are given an array A of n integers (A1, A2 , ... , An) and some queries. In each query, you will be given an integer D. Your task is to find an integer Ai (1 ≤ i ≤ n) such that XOR operation between D and Ai gives the maximum result. According to Wikipedia, "Exclusive or or exclusive disjunction is a logical operation that outputs true only when inputs differ (one is true, the other is false)".

Input

The first line contains an integer n (1 ≤ n ≤ 105), the number of integers in the array.
The next line contains n space-separated non-negative integers. Each of them is unique and less than 231.
The next line contains an integer Q (1 ≤ Q  ≤ 105), the number of queries.
Each of the next Q lines contains a non-negative integer D (D < 231).

Output

For each query, you have to print "Query X: Y Z" (without the quotation marks), where X is the query number starting from 1, Y is the index number of the selected integer from the array and Z is the XOR result that was maximum.

Sample

InputOutput
5
3 4 8 13 6
2
4
11
Query 1: 3 12
Query 2: 2 15

Notes: For first query, 4 gives

3 XOR 4 = 7,
4 XOR 4 = 0,
8 XOR 4 = 12,
13 XOR 4 = 9,
6 XOR 4 = 2,

Here, the index of 8 is 3 in the array and the result is 12 which is maximum.


Discussion

Statistics


73% Solution Ratio

dip_BRUREarliest, Dec '19

RamprosadGFastest, 0.0s

S_SubrataLightest, 4.0 MB

saidur_sajolShortest, 1058B

Submit

Login to submit

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