You are given an array of n integers (, , ..., ) and some queries. In each query, you will be given an integer . Your task is to find an integer () such that XOR operation between and 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 (), 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 . The next line contains an integer (), the number of queries. Each of the next lines contains a non-negative integer ().
For each query, you have to print (without the quotation marks), where is the query number starting from , is the index number of the selected integer from the array and is the XOR result that was maximum.
Input | Output |
---|---|
5 3 4 8 13 6 2 4 11 | Query 1: 3 12 Query 2: 2 15 |
For first query, 4 gives
Here, the index of 8 is 3 in the array and the result is 12 which is maximum. |