Limits 1s, 512 MB

You are given an array AA of n integers (A1A_1, A2A_2, ..., AnA_n) and some queries. In each query, you will be given an integer DD. Your task is to find an integer AiA_i (1in1 ≤ i ≤ n) such that XOR operation between DD and AiA_i 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)".


The first line contains an integer nn (1n1051 ≤ n ≤ 10^5), 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 2312^{31}. The next line contains an integer QQ (1Q1051 ≤ Q  ≤ 10^5), the number of queries. Each of the next QQ lines contains a non-negative integer DD (D<231D < 2^{31}).


For each query, you have to print Query X: Y Z\texttt{Query X: Y Z} (without the quotation marks), where XX is the query number starting from 11, YY is the index number of the selected integer from the array and ZZ is the XOR result that was maximum.


3 4 8 13 6
Query 1: 3 12
Query 2: 2 15

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.


Login to submit.



79% Solution Ratio
dip_BRUREarliest, Dec '19
AlveRahmanFastest, 0.0s
S_SubrataLightest, 4.0 MB
dev_shajidShortest, 980B
Toph uses cookies. By continuing you agree to our Cookie Policy.