We’re preparing your current view and syncing the latest data.
You are given an array of integers. For each query integer, find the maximum XOR value obtained by XORing the query integer with any element in the array. Implement a solution that can efficiently handle multiple queries.
The first line contains an integer n, the number of elements in the array. The second line contains n integers, the elements of the array. The third line contains an integer q, the number of queries. The next q lines each contain a single integer representing the query value.
For each query, output a single integer — the maximum XOR value obtainable with the query integer and any element in the array.
1 ≤ n, q ≤ 10^5; 0 ≤ array elements, query values ≤ 10^9
Example 1
Input
3 5 1 7 3 2 0 4
Output
7 7 7
Explanation
For query 2, max XOR is 2 XOR 5 = 7. For query 0, max XOR is 0 XOR 7 = 7. For query 4, max XOR is 4 XOR 3 = 7.