#250HardTries· Binary Trie with Offline Queries

Max XOR Under a Limit

A signal-processing lab stores a set of calibration codes (non-negative integers). To test a new reading `x`, an engineer wants the stored code that, combined with `x` by bitwise XOR, gives the **largest possible result**. But only codes up to a given limit `m` are allowed for that test, because larger codes belong to a newer hardware revision. You get the stored codes `nums` and a list of queries `[x, m]`. For each query return the maximum value of `x XOR nums[i]` over all `i` with `nums[i] <= m`. If no code is allowed, the answer for that query is `-1`. The answers must be returned in the order of the queries.

Input format

`nums`: an array of non-negative integers; `queries`: an array of pairs `[x, m]`.

Output format

An array with one integer per query: the largest XOR value, or -1 when no code is at most m.

Examples

Input: nums = [0, 1, 2, 3, 4], queries = [[3, 1], [1, 3], [5, 6]]

Output: [3, 3, 7]

For [3,1] the allowed codes are 0 and 1: 3^0=3 and 3^1=2, the best is 3. For [1,3] the allowed codes are 0..3 and 1^2=3 is the best. For [5,6] all codes are allowed and 5^2=7 is the best.

Input: nums = [5, 2, 4, 6, 6, 3], queries = [[12, 4], [8, 1], [6, 3]]

Output: [15, -1, 5]

For [12,4] the allowed codes are 2, 3 and 4: 12^3=15 is the best. For [8,1] no code is at most 1, so -1. For [6,3] the allowed codes are 2 and 3: 6^2=4 and 6^3=5, so 5.

Constraints

1 <= nums.length <= 10^5
1 <= queries.length <= 10^5
0 <= nums[i], x < 2^30
0 <= m < 2^30

Study first

Tries (Prefix Trees)

#trie
#bit-manipulation
#offline-queries
#sorting
#xor