Minimum XOR
Problem
You are given q queries of two types:
- 1 X: Append value X into an array.
- 2 X K: You are required to print the Kth minimum XOR of X with the current array.
You have to make a new array whose ith element is current_array[i]X. Then sort it and print the Kth element.
Input format
- The first line contains q (1≤q≤100000).
- Next q lines contain the types of queries. (1 or 2)
- If type is 1, then it contains X (1≤X≤10e18).
- If type is 2, then it contains X (1≤X≤10e18) and K (K≤current array size).
Output format
Print the number in the second type of query.
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation
After 1st Query array will be : 5.
After 2nd Query array will be : 5 3.
After 3rd Query array will be : 5 3 2.
After 4th Query array will be : 5 3 2 9.
In 5th Query XOR with 8 indivisual make temp array : 13(5^8) 11(3^8) 10(2^8) 1(9^8).
Sort it: 1 10 11 13 and 3rd element is 11.
After 6th Query array will be : 5 3 2 9 89.
After 7th Query array will be : 5 3 2 9 89 56.
In 8th Query XOR with 8 indivisual make temp array : 80(5^85) 86(3^85) 87(2^85) 92(9^85) 12(89^85) 109(56^85).
Sort it: 12 80 86 87 92 109 and 5rd element is 92.
