<p>Given an integer array <code>nums</code>, return <em>the maximum result of </em><code>nums[i] XOR nums[j]</code>, where <code>0 &lt;= i &lt;= j &lt; n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,10,5,25,2,8]
<strong>Output:</strong> 28
<strong>Explanation:</strong> The maximum result is 5 XOR 25 = 28.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [14,70,53,83,49,91,36,80,92,51,66,70]
<strong>Output:</strong> 127
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # sort nums
        # binary search for mi in nums; then restrict next searchs from 0 to mi

        # Ideal number has opposite bits from xi in each position
        # get search range for ideal leading bit; restrict search space if we find one, otherwise just move to next bit
        # O(nlogn + qlogn)
        q = len(queries)
        nums = list(set(nums))
        nums.sort()
        answer = [0]*q
        for i, (x, m) in enumerate(queries):
            #print("NEW QUERY")
            #print(i, x, m)
            hi = bisect.bisect_right(nums, m)
            # handle edge cases now
            if hi == 0:
                answer[i] = -1
                continue
            if hi == 1:
                answer[i] = x ^ nums[0]
                continue
            lo = 0
            goal = ~x
            xlen = x.bit_length() - 1
            bit = nums[hi - 1].bit_length() - 1
            maxVal = 0
            # we maintain the invariant that the elements in [lo, high] have all the same bits before bit
            # so searching for things with the desired bit is just a binary search
            while bit >= 0:
                mask = 1 << bit
                goalbit = mask if bit > xlen else goal & mask
                key = lambda v : v & mask
                bit -= 1
                #print(lo, hi)
                left = bisect.bisect_left(nums, goalbit, lo = lo, hi = hi, key = key)
                # if we found nothing with the bit we want, or everything has bit we want, we cant narrow the search space
                if left == hi:
                    continue
                right = bisect.bisect_right(nums, goalbit, lo = left, hi = hi, key = key)
                if right == lo:
                    continue
                lo = left
                hi = right
                if lo == hi - 1:
                    answer[i] = x ^ nums[lo]
                    break
            # the only case where we didn't break from the loop early is if we never found anything with a bit in common with goal
            # in which case we want answer[i] to be 0, which we already set it to
        return answer
    def findMaximumXOR(self, nums: List[int]) -> int:
        maxVal = max(nums)
        return max(self.maximizeXor(nums, [[num, maxVal] for num in nums]))
62128