Tries (Prefix Trees)

struct TrieNode {
    TrieNode* children[26];   // One slot per lowercase letter
    bool isEnd;               // True if this node is end of a valid word
    int count;                // Optional: word frequency / subtree word count
 
    TrieNode() : isEnd(false), count(0) {
        fill(begin(children), end(children), nullptr);
    }
};

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
    struct Node {
        Node* ch[26]{};     // All nullptr by default
        bool end = false;
    };
    Node* root;
 
public:
    Trie() : root(new Node()) {}
 
    void insert(const string& word) {
        Node* curr = root;
        for (char c : word) {
            int i = c - 'a';
            if (!curr->ch[i]) curr->ch[i] = new Node();
            curr = curr->ch[i];
        }
        curr->end = true;
    }
 
    bool search(const string& word) {
        Node* curr = root;
        for (char c : word) {
            int i = c - 'a';
            if (!curr->ch[i]) return false;
            curr = curr->ch[i];
        }
        return curr->end;
    }
 
    bool startsWith(const string& prefix) {
        Node* curr = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (!curr->ch[i]) return false;
            curr = curr->ch[i];
        }
        return true;   // Any node reachable via prefix is valid
    }
};
// insert, search, startsWith: O(m) time — m = word/prefix length
// Space: O(N × M × 26) worst case — N words, average length M

class Trie {
    struct Node {
        Node* ch[26]{};
        bool end = false;
    };
    Node* root = new Node();
 
public:
    // INSERT — O(m) time, O(m) space (new nodes created)
    void insert(const string& word) {
        Node* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->ch[idx])
                curr->ch[idx] = new Node();    // Create node if missing
            curr = curr->ch[idx];
        }
        curr->end = true;                       // Mark end of word
    }
 
    // SEARCH — O(m) time, O(1) space
    bool search(const string& word) {
        Node* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->ch[idx]) return false;   // Character missing → not in trie
            curr = curr->ch[idx];
        }
        return curr->end;   // Must reach end of a valid word (not just prefix)
    }
 
    // STARTSWITH — O(m) time, O(1) space
    bool startsWith(const string& prefix) {
        Node* curr = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!curr->ch[idx]) return false;
            curr = curr->ch[idx];
        }
        return true;   // Any reachable node confirms prefix exists
    }
 
    // HELPER — Find the node at the end of a prefix (returns nullptr if absent)
    Node* findPrefix(const string& prefix) {
        Node* curr = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!curr->ch[idx]) return nullptr;
            curr = curr->ch[idx];
        }
        return curr;
    }
};

struct TrieNode {
    TrieNode* ch[26]{};
    int wordCount  = 0;    // How many words end exactly here
    int prefixCount = 0;   // How many words pass through here
};
 
class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int i = c - 'a';
            if (!curr->ch[i]) curr->ch[i] = new TrieNode();
            curr = curr->ch[i];
            curr->prefixCount++;    // Every node on the path
        }
        curr->wordCount++;          // Only at the end node
    }
 
    // Count words with given prefix
    int countWordsWithPrefix(const string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (!curr->ch[i]) return 0;
            curr = curr->ch[i];
        }
        return curr->prefixCount;
    }
 
    // Count exact word occurrences
    int countWord(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int i = c - 'a';
            if (!curr->ch[i]) return 0;
            curr = curr->ch[i];
        }
        return curr->wordCount;
    }
};

// Returns true if the current node should be deleted (has no children, not end)
bool deleteWord(TrieNode* curr, const string& word, int depth) {
    if (!curr) return false;
 
    if (depth == (int)word.size()) {
        if (!curr->isEnd) return false;   // Word doesn't exist
        curr->isEnd = false;              // Unmark end
 
        // Delete this node only if it has no children
        for (auto* child : curr->children)
            if (child) return false;      // Has children — keep this node
        return true;                      // No children — safe to delete
    }
 
    int idx = word[depth] - 'a';
    if (deleteWord(curr->children[idx], word, depth + 1)) {
        delete curr->children[idx];
        curr->children[idx] = nullptr;
 
        // Delete this node if: not end of another word AND no children left
        if (!curr->isEnd) {
            for (auto* child : curr->children)
                if (child) return false;
            return true;
        }
    }
    return false;
}
 
void remove(const string& word) {
    deleteWord(root, word, 0);
}
// Time: O(m), Space: O(m) — recursion stack

// Collect all words in the subtree rooted at 'node'
void collectWords(TrieNode* node, string& current, vector<string>& results) {
    if (!node) return;
    if (node->isEnd) results.push_back(current);
 
    for (int i = 0; i < 26; i++) {
        if (node->ch[i]) {
            current.push_back('a' + i);
            collectWords(node->ch[i], current, results);
            current.pop_back();   // Backtrack
        }
    }
}
 
vector<string> autocomplete(const string& prefix) {
    TrieNode* node = findPrefix(prefix);
    if (!node) return {};
 
    vector<string> results;
    string current = prefix;
    collectWords(node, current, results);
    return results;   // All words that start with prefix
}
// Time: O(m + total characters in matching words)

string replaceWords(vector<string>& dictionary, string sentence) {
    // Build trie of roots
    Trie trie;
    for (const string& root : dictionary) trie.insert(root);
 
    istringstream iss(sentence);
    string word, result;
 
    while (iss >> word) {
        // Traverse trie to find shortest prefix match
        TrieNode* curr = trie.root;
        string replacement = "";
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->ch[idx]) break;     // No prefix match — use full word
            curr = curr->ch[idx];
            replacement += c;
            if (curr->isEnd) break;        // Found a root! Replace with it
        }
        if (!result.empty()) result += " ";
        result += (curr->isEnd ? replacement : word);
    }
    return result;
}
// Time: O(total chars in dictionary + total chars in sentence)
// Space: O(total chars in dictionary)

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    struct Node {
        Node* ch[26]{};
        string* word = nullptr;   // Stores the word if this is an end node
    };
 
    // Build Trie
    Node* root = new Node();
    for (string& w : words) {
        Node* curr = root;
        for (char c : w) {
            if (!curr->ch[c-'a']) curr->ch[c-'a'] = new Node();
            curr = curr->ch[c-'a'];
        }
        curr->word = &w;
    }
 
    int rows = board.size(), cols = board[0].size();
    vector<string> result;
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
 
    function<void(int, int, Node*)> dfs = [&](int r, int c, Node* node) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        char ch = board[r][c];
        if (ch == '#' || !node->ch[ch-'a']) return;    // Visited or no path
 
        node = node->ch[ch-'a'];
        if (node->word) {
            result.push_back(*node->word);
            node->word = nullptr;   // Avoid duplicates — prune found word
        }
 
        board[r][c] = '#';         // Mark visited
        for (int d = 0; d < 4; d++) dfs(r+dx[d], c+dy[d], node);
        board[r][c] = ch;          // Restore (backtrack)
    };
 
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            dfs(r, c, root);
 
    return result;
}
// Time: O(M × 4 × 3^(L-1)) per starting cell — M=board cells, L=max word length
// Trie pruning makes this much faster in practice than pure DFS
// Space: O(N × L) for trie — N words, L average length

class WordDictionary {
    struct Node {
        Node* ch[26]{};
        bool end = false;
    };
    Node* root = new Node();
 
public:
    void addWord(const string& word) {
        Node* curr = root;
        for (char c : word) {
            if (!curr->ch[c-'a']) curr->ch[c-'a'] = new Node();
            curr = curr->ch[c-'a'];
        }
        curr->end = true;
    }
 
    bool search(const string& word) {
        return dfs(root, word, 0);
    }
 
private:
    bool dfs(Node* node, const string& word, int i) {
        if (!node) return false;
        if (i == (int)word.size()) return node->end;
 
        char c = word[i];
        if (c == '.') {
            // Wildcard: try all possible children
            for (int j = 0; j < 26; j++)
                if (dfs(node->ch[j], word, i+1)) return true;
            return false;
        }
        return dfs(node->ch[c-'a'], word, i+1);
    }
};
// addWord: O(m), search: O(m) best case, O(26^m) worst case (all wildcards)

struct BitTrieNode {
    BitTrieNode* ch[2]{};   // ch[0] for bit=0, ch[1] for bit=1
};
 
class BitTrie {
    BitTrieNode* root = new BitTrieNode();
    static const int BITS = 31;   // For 32-bit non-negative integers
 
public:
    void insert(int num) {
        BitTrieNode* curr = root;
        for (int i = BITS; i >= 0; i--) {    // MSB to LSB
            int bit = (num >> i) & 1;
            if (!curr->ch[bit]) curr->ch[bit] = new BitTrieNode();
            curr = curr->ch[bit];
        }
    }
 
    // Returns the maximum XOR achievable with num using any number in the trie
    int maxXOR(int num) {
        BitTrieNode* curr = root;
        int result = 0;
 
        for (int i = BITS; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int want = 1 - bit;     // Prefer opposite bit for XOR = 1
 
            if (curr->ch[want]) {
                result |= (1 << i);   // This bit of XOR is 1
                curr = curr->ch[want];
            } else {
                curr = curr->ch[bit]; // Must take same bit (XOR = 0 for this bit)
            }
        }
        return result;
    }
};
// insert: O(32) = O(1), maxXOR: O(32) = O(1)
// Space: O(n × 32) where n = number of integers inserted

int findMaximumXOR(vector<int>& nums) {
    BitTrie trie;
    for (int x : nums) trie.insert(x);
 
    int maxVal = 0;
    for (int x : nums) {
        maxVal = max(maxVal, trie.maxXOR(x));
    }
    return maxVal;
}
// Time: O(n × 32) = O(n), Space: O(n × 32) = O(n)
 
/*
  nums = [3, 10, 5, 25, 2, 8]
  Binary: 00011, 01010, 00101, 11001, 00010, 01000
 
  For num=5 (00101), maxXOR seeks:
  Bit 4: want 1, have 1 (from 25=11001) → take it, result bit 4 = 1
  Bit 3: want 0, have 0 (from 25=11001) → take it, result bit 3 = 0... 
  
  Maximum XOR = 5 XOR 25 = 28
*/

// Find subarray with maximum XOR using prefix XOR + Bit Trie
int maxXORSubarray(vector<int>& nums) {
    BitTrie trie;
    trie.insert(0);   // Empty prefix (XOR = 0)
 
    int prefixXOR = 0, maxXOR = 0;
    for (int x : nums) {
        prefixXOR ^= x;
        maxXOR = max(maxXOR, trie.maxXOR(prefixXOR));
        trie.insert(prefixXOR);
    }
    return maxXOR;
}
// Time: O(n × 32) = O(n), Space: O(n × 32) = O(n)
// Key: XOR of subarray [i+1..j] = prefix[j] XOR prefix[i]
//      To maximize prefix[j] XOR prefix[i], for each j find best prefix[i] in trie

// Conceptual structure (not typically implemented from scratch in interviews)
struct CompressedNode {
    unordered_map<char, pair<string, CompressedNode*>> children;
    // key: first char of edge, value: (edge label, child node)
    bool isEnd = false;
};

class Trie {
    struct Node { Node* ch[26]{}; bool end=false; };
    Node* root = new Node();
public:
    void insert(const string& w) {
        Node* c = root;
        for (char x : w) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
        }
        c->end = true;
    }
    bool search(const string& w) {
        Node* c = root;
        for (char x : w) {
            if (!c->ch[x-'a']) return false;
            c = c->ch[x-'a'];
        }
        return c->end;
    }
    bool startsWith(const string& p) {
        Node* c = root;
        for (char x : p) {
            if (!c->ch[x-'a']) return false;
            c = c->ch[x-'a'];
        }
        return true;
    }
};
// All operations: O(m) time, O(1) extra space (besides insert's O(m) node creation)

string longestWord(vector<string>& words) {
    Trie trie;
    for (const string& w : words) trie.insert(w);
 
    string best = "";
    // BFS/DFS from root — only follow nodes that are marked as word ends
    // This ensures every prefix is a valid word
 
    // Sort to ensure lexicographically smallest is chosen first
    sort(words.begin(), words.end());
 
    for (const string& w : words) {
        if (w.size() > best.size() || (w.size() == best.size() && w < best)) {
            // Verify every prefix is also in the trie as a word
            bool valid = true;
            string prefix;
            for (char c : w) {
                prefix += c;
                if (!trie.search(prefix)) { valid = false; break; }
            }
            if (valid) best = w;
        }
    }
    return best;
}
// Time: O(n × m log(n×m)) sorting + O(n × m²) verification
// Better: use Trie directly with BFS
 
// Optimal Trie-based solution:
string longestWord_Trie(vector<string>& words) {
    struct Node { Node* ch[26]{}; bool end=false; };
    Node* root = new Node();
    for (const string& w : words) {
        Node* c = root;
        for (char x : w) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
        }
        c->end = true;
    }
 
    string best = "", curr = "";
    function<void(Node*)> dfs = [&](Node* node) {
        if (curr.size() > best.size()) best = curr;
        for (int i = 0; i < 26; i++) {
            if (node->ch[i] && node->ch[i]->end) {
                curr += ('a' + i);
                dfs(node->ch[i]);
                curr.pop_back();
            }
        }
    };
    dfs(root);   // DFS only through nodes that are ends of valid words
    return best;
}
// Time: O(N) — N = total characters. Space: O(N).

string replaceWords(vector<string>& dict, string sentence) {
    struct Node { Node* ch[26]{}; bool end=false; };
    Node* root = new Node();
    for (const string& root_w : dict) {
        Node* c = root;
        for (char x : root_w) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
        }
        c->end = true;
    }
 
    string result;
    istringstream iss(sentence);
    string word;
    while (iss >> word) {
        if (!result.empty()) result += ' ';
        Node* c = root;
        bool replaced = false;
        string prefix;
        for (char ch : word) {
            if (!c->ch[ch-'a']) break;
            c = c->ch[ch-'a'];
            prefix += ch;
            if (c->end) { result += prefix; replaced = true; break; }
        }
        if (!replaced) result += word;
    }
    return result;
}
// Time: O(D + S) where D = total dict chars, S = total sentence chars
// Space: O(D) for trie

class MapSum {
    struct Node {
        Node* ch[26]{};
        int val = 0;        // Value stored at this word end
        int prefixSum = 0;  // Sum of all values in subtree
    };
    Node* root = new Node();
    unordered_map<string, int> prevVal;  // Track previous value for updates
 
public:
    void insert(const string& key, int val) {
        int delta = val - prevVal[key];   // Delta from previous value
        prevVal[key] = val;
 
        Node* c = root;
        for (char x : key) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
            c->prefixSum += delta;        // Update all nodes on path
        }
        c->val += delta;
    }
 
    int sum(const string& prefix) {
        Node* c = root;
        for (char x : prefix) {
            if (!c->ch[x-'a']) return 0;
            c = c->ch[x-'a'];
        }
        return c->prefixSum;
    }
};
// insert: O(m), sum: O(m) — m = key/prefix length

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    sort(products.begin(), products.end());   // Lexicographic order
 
    struct Node {
        Node* ch[26]{};
        vector<string*> suggestions;   // Up to 3 suggestions
    };
    Node* root = new Node();
 
    for (string& p : products) {
        Node* c = root;
        for (char x : p) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
            if (c->suggestions.size() < 3) c->suggestions.push_back(&p);
        }
    }
 
    vector<vector<string>> result;
    Node* c = root;
    for (char x : searchWord) {
        if (c) c = c->ch[x-'a'];     // Advance (or null out if no match)
        result.emplace_back();
        if (c) for (string* s : c->suggestions) result.back().push_back(*s);
    }
    return result;
}
// Time: O(n log n) sort + O(N) build + O(m × 3) query — N=total chars, m=search length
// Space: O(N) for trie

int findMaximumXOR(vector<int>& nums) {
    struct Node { Node* ch[2]{}; };
    Node* root = new Node();
 
    auto insert = [&](int num) {
        Node* c = root;
        for (int i = 31; i >= 0; i--) {
            int b = (num >> i) & 1;
            if (!c->ch[b]) c->ch[b] = new Node();
            c = c->ch[b];
        }
    };
    auto maxXOR = [&](int num) {
        Node* c = root;
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            int b = (num >> i) & 1, want = 1 - b;
            if (c->ch[want]) { res |= (1 << i); c = c->ch[want]; }
            else if (c->ch[b]) c = c->ch[b];
            else break;
        }
        return res;
    };
 
    for (int x : nums) insert(x);
    int best = 0;
    for (int x : nums) best = max(best, maxXOR(x));
    return best;
}
// Time: O(n × 32) = O(n), Space: O(n × 32)

class WordDictionary {
    struct Node { Node* ch[26]{}; bool end=false; };
    Node* root = new Node();
 
    bool dfs(Node* n, const string& w, int i) {
        if (!n) return false;
        if (i == (int)w.size()) return n->end;
        char c = w[i];
        if (c == '.') {
            for (int j = 0; j < 26; j++)
                if (dfs(n->ch[j], w, i+1)) return true;
            return false;
        }
        return dfs(n->ch[c-'a'], w, i+1);
    }
public:
    void addWord(const string& w) {
        Node* c = root;
        for (char x : w) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
        }
        c->end = true;
    }
    bool search(const string& w) { return dfs(root, w, 0); }
};
// addWord: O(m), search: O(m) best, O(26^m) worst (all wildcards)

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    struct Node { Node* ch[26]{}; string word; };
    Node* root = new Node();
    for (string& w : words) {
        Node* c = root;
        for (char x : w) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
        }
        c->word = w;
    }
 
    int R = board.size(), C = board[0].size();
    vector<string> result;
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
 
    function<void(int,int,Node*)> dfs = [&](int r, int c, Node* node) {
        char ch = board[r][c];
        if (ch=='#' || !node->ch[ch-'a']) return;
        node = node->ch[ch-'a'];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word.clear();   // Remove to avoid duplicate
        }
        board[r][c] = '#';
        for (int d=0; d<4; d++) {
            int nr=r+dx[d], nc=c+dy[d];
            if (nr>=0&&nr<R&&nc>=0&&nc<C) dfs(nr,nc,node);
        }
        board[r][c] = ch;
    };
 
    for (int r=0; r<R; r++)
        for (int c=0; c<C; c++)
            dfs(r, c, root);
    return result;
}
// Time: O(M × 4 × 3^(L-1)) — M=board cells, L=max word length
// Trie pruning eliminates dead branches early

vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
    // Build trie of all words
    struct Node { Node* ch[26]{}; bool end=false; };
    Node* root = new Node();
 
    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // Process shorter words first
    });
 
    auto insert = [&](const string& w) {
        Node* c = root;
        for (char x : w) {
            if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
            c = c->ch[x-'a'];
        }
        c->end = true;
    };
 
    // DP: can word[i..] be formed by 2+ words already in trie?
    function<bool(const string&, int, int)> canForm =
        [&](const string& w, int start, int count) -> bool {
        if (start == (int)w.size()) return count >= 2;
        Node* c = root;
        for (int i = start; i < (int)w.size(); i++) {
            if (!c->ch[w[i]-'a']) return false;
            c = c->ch[w[i]-'a'];
            if (c->end && canForm(w, i+1, count+1)) return true;
        }
        return false;
    };
 
    vector<string> result;
    for (const string& w : words) {
        if (!w.empty() && canForm(w, 0, 0)) result.push_back(w);
        insert(w);   // Add to trie after checking (shorter words only)
    }
    return result;
}
// Time: O(n log n sort + sum(L²) for DP per word)
// Space: O(total chars) for trie

// Trie approach: for each word w, check if any suffix of w reversed exists in trie,
// and the prefix of w forms a palindrome (or vice versa).
// Simplified hash-map approach for interviews:
vector<vector<int>> palindromePairs(vector<string>& words) {
    unordered_map<string, int> wordIdx;
    for (int i = 0; i < (int)words.size(); i++) wordIdx[words[i]] = i;
 
    auto isPalin = [](const string& s, int l, int r) {
        while (l < r) if (s[l++] != s[r--]) return false;
        return true;
    };
 
    vector<vector<int>> result;
    for (int i = 0; i < (int)words.size(); i++) {
        const string& w = words[i];
        int n = w.size();
        for (int k = 0; k <= n; k++) {
            // Case 1: Reverse of words[i][0..k-1] + words[i][k..n-1] is palindrome
            //         → words[i][k..n-1] is palindrome, reverse of words[i][0..k-1] exists
            if (isPalin(w, k, n-1)) {
                string revPrefix = string(w.begin(), w.begin()+k);
                reverse(revPrefix.begin(), revPrefix.end());
                if (wordIdx.count(revPrefix) && wordIdx[revPrefix] != i)
                    result.push_back({i, wordIdx[revPrefix]});
            }
            // Case 2: words[i][0..k-1] is palindrome, reverse of words[i][k..n-1] exists
            if (k > 0 && isPalin(w, 0, k-1)) {
                string revSuffix = string(w.begin()+k, w.end());
                reverse(revSuffix.begin(), revSuffix.end());
                if (wordIdx.count(revSuffix) && wordIdx[revSuffix] != i)
                    result.push_back({wordIdx[revSuffix], i});
            }
        }
    }
    return result;
}
// Time: O(n × k²) where k = max word length. Space: O(n).

// Key insight: Build trie of REVERSED words. Match from current char backwards.
class StreamChecker {
    struct Node { Node* ch[26]{}; bool end=false; };
    Node* root = new Node();
    string stream;
 
public:
    StreamChecker(vector<string>& words) {
        for (string& w : words) {
            reverse(w.begin(), w.end());   // Insert reversed words
            Node* c = root;
            for (char x : w) {
                if (!c->ch[x-'a']) c->ch[x-'a'] = new Node();
                c = c->ch[x-'a'];
            }
            c->end = true;
        }
    }
 
    bool query(char letter) {
        stream += letter;
        Node* c = root;
        // Traverse stream backwards through reversed-word trie
        for (int i = stream.size()-1; i >= 0 && c; i--) {
            c = c->ch[stream[i]-'a'];
            if (c && c->end) return true;
        }
        return false;
    }
};
// query: O(max word length) — traverses at most L characters of stream
// Space: O(total chars in all words)

// Process queries offline sorted by m; insert elements into Bit Trie incrementally
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    sort(nums.begin(), nums.end());
    int q = queries.size();
    vector<int> idx(q);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return queries[a][1] < queries[b][1];
    });
 
    struct Node { Node* ch[2]{}; };
    Node* root = new Node();
    auto insert = [&](int num) {
        Node* c = root;
        for (int i=31; i>=0; i--) {
            int b=(num>>i)&1;
            if (!c->ch[b]) c->ch[b]=new Node();
            c=c->ch[b];
        }
    };
    auto maxXOR = [&](int num) {
        Node* c = root;
        int res = 0;
        for (int i=31; i>=0; i--) {
            int b=(num>>i)&1, want=1-b;
            if (c->ch[want]) { res|=(1<<i); c=c->ch[want]; }
            else if (c->ch[b]) c=c->ch[b];
            else break;
        }
        return res;
    };
 
    vector<int> result(q);
    int ni = 0;
    for (int qi : idx) {
        int x=queries[qi][0], m=queries[qi][1];
        while (ni < (int)nums.size() && nums[ni] <= m) insert(nums[ni++]);
        result[qi] = (ni == 0) ? -1 : maxXOR(x);
    }
    return result;
}
// Time: O((n + q) log(n + q) + (n + q) × 32)
// Space: O(n × 32)