A radio lab keeps quartz crystals, each labelled with a non-negative integer code in crystals.
A tuning request is a pair [signal, cap]. The request may only use a crystal whose code is
at most cap, and its quality is signal XOR code (signal ^ code in Python). For every request
return the largest quality it can reach, or -1 if no crystal has a code <= cap.
Return the answers as a list in the order the requests were given.
Examples
Input: crystals = [0, 1, 2, 3, 4], requests = [[3, 1], [1, 3], [5, 6]]
Output: [3, 3, 7]
Explanation: request [3, 1] may use codes 0 and 1: 3 ^ 0 = 3 is best.
[1, 3] may use 0..3: 1 ^ 2 = 3. [5, 6] may use all five: 5 ^ 2 = 7.
Input: crystals = [5, 2, 4, 6, 6, 3], requests = [[12, 4], [8, 1], [6, 3]]
Output: [15, -1, 5]
Explanation: [8, 1] has no crystal with code <= 1.
Constraints
0 <= len(crystals), len(requests) <= 2 * 10**40 <= crystals[i], signal, cap < 2**30- Target: about
O((n + q) * 30)after sorting; testing every crystal for every request is too slow
Goals
- Answer maximum-XOR queries greedily with a binary trie
- Handle an upper bound on the partner by sorting queries and inserting values lazily
- Detect queries that have no valid partner at all