<p>You are given an array <code>nums</code> consisting of non-negative integers. You are also given a <code>queries</code> array, where <code>queries[i] = [x<sub>i</sub>, m<sub>i</sub>]</code>.</p>

<p>The answer to the <code>i<sup>th</sup></code> query is the maximum bitwise <code>XOR</code> value of <code>x<sub>i</sub></code> and any element of <code>nums</code> that does not exceed <code>m<sub>i</sub></code>. In other words, the answer is <code>max(nums[j] XOR x<sub>i</sub>)</code> for all <code>j</code> such that <code>nums[j] &lt;= m<sub>i</sub></code>. If all elements in <code>nums</code> are larger than <code>m<sub>i</sub></code>, then the answer is <code>-1</code>.</p>

<p>Return <em>an integer array </em><code>answer</code><em> where </em><code>answer.length == queries.length</code><em> and </em><code>answer[i]</code><em> is the answer to the </em><code>i<sup>th</sup></code><em> query.</em></p>

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

<pre>
<strong>Input:</strong> nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
<strong>Output:</strong> [3,3,7]
<strong>Explanation:</strong>
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
</pre>

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

<pre>
<strong>Input:</strong> nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
<strong>Output:</strong> [15,-1,5]
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length, queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= nums[j], x<sub>i</sub>, m<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    """
    it is similar to https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

    for each query, we will insert the numbers in nums which are less than mi, so that we only
    have to deal with lesser numbers

    then we start traversing trie for query x_i.
        if available: 
            choose opposite bit of X_i
        else: 
            choose whichever available
        [same as https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/]

    """
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:

        trie = [[], []] # zero, one

        def insert(num):
            nonlocal trie
            curr = trie
            for i in range(31, -1, -1):
                bit = 1 if (1<<i & num) else 0
                if not curr[bit]:
                    curr[bit] = [[], []]
                curr = curr[bit]

        def search_max_xor(x):
            nonlocal trie
            curr_maxxor = 0
            curr = trie
            for i in range(31, -1, -1):
                xbit = 1 if (1<<i & x) else 0
                opposite = 1 if (xbit == 0) else 0
                if curr[opposite]:
                    curr_maxxor += 1<<i
                    curr = curr[opposite]
                else:
                    curr = curr[xbit]
            return curr_maxxor
        
        nums.sort() # to only insert the numbers which are smaller
        # to process entries with lower m value first, so that we don't insert higher values in trie
        queries_copy = [[queries[i][0], queries[i][1], i] for i in range(len(queries))]
        queries_copy.sort(key = lambda a:a[1]) 
        i = 0 # to keep track of how many numbers inserted
        n = len(nums)        
        answers = [None for _ in range(len(queries))]

        for query in queries_copy:
            x, m, idx = query[0], query[1], query[2]

            while i < n and nums[i] <= m:
                insert(nums[i])
                i += 1
            
            if i == 0:
                # because of condition "If all elements in nums are larger than mi, then the answer is -1."
                answers[idx] = -1
            else:
                answers[idx] = search_max_xor(x)

        return answers
146433