#include <bits/stdc++.h>
using namespace std;

// ===================================================================
// This file contains a collection of algorithms based on the
// Persistent Binary Trie (also known as Persistent 01-Trie).
// Each function is ready to be used as a "black box".
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// ===================================================================

// ===================================================================
// 1) Core Structure: Persistent Binary Trie
//    This is the underlying data structure used by all the functions
//    below. It supports creating new versions by inserting numbers and
//    allows querying a specific version for XOR-related problems.
//    The number of bits is fixed at compile time via MAX_LOG.
// ===================================================================

// 1.1) Persistent Binary Trie Node and Class
//      Parameters:
//        - MAX_LOG: The number of bits to consider (e.g., 30 for 32-bit integers).
//                   All numbers inserted must fit within these bits.
//      Returns:
//        - An object that can be used to build versions and answer queries.
//      Time complexity: O(MAX_LOG) per insertion or query.
//      Constraint: The class must be instantiated with a suitable MAX_LOG.
//      Note: This is the core structure; you don't call it directly,
//            but the functions below use it.
template<int MAX_LOG>
struct PersistentBinaryTrie {
    struct Node {
        int child[2]; // child[0] for bit 0, child[1] for bit 1
        int cnt;      // number of numbers in this subtree
        Node() {
            child[0] = child[1] = 0;
            cnt = 0;
        }
    };

    vector<Node> tree; // array of nodes
    vector<int> root;  // root node index for each version
    int versionCount;  // number of versions created

    PersistentBinaryTrie() {
        tree.reserve(5000000); // reserve memory to avoid reallocation
        tree.push_back(Node()); // node 0 is the null node
        root.push_back(0);      // version 0 is empty
        versionCount = 0;
    }

    // Insert a number 'num' into the trie, creating a new version.
    // Returns the index of the new root.
    int insert(int prevRoot, int num) {
        int newRoot = tree.size();
        tree.push_back(tree[prevRoot]); // copy the previous root
        int cur = newRoot;
        int prev = prevRoot;
        tree[cur].cnt++;

        for (int bit = MAX_LOG; bit >= 0; bit--) {
            int b = (num >> bit) & 1;
            // Create a new node for the child
            int newChild = tree.size();
            tree.push_back(tree[tree[prev].child[b]]);
            tree[cur].child[b] = newChild;
            tree[newChild].cnt++;

            // Move to the next level
            cur = newChild;
            prev = tree[prev].child[b];
        }
        return newRoot;
    }

    // Query the maximum XOR of 'num' with any number in a specific version.
    int queryMaxXor(int rootIdx, int num) {
        int cur = rootIdx;
        int ans = 0;
        for (int bit = MAX_LOG; bit >= 0; bit--) {
            int b = (num >> bit) & 1;
            // Prefer the opposite bit to maximize XOR
            if (tree[tree[cur].child[b ^ 1]].cnt > 0) {
                ans |= (1 << bit);
                cur = tree[cur].child[b ^ 1];
            } else {
                cur = tree[cur].child[b];
            }
        }
        return ans;
    }

    // Query the minimum XOR of 'num' with any number in a specific version.
    int queryMinXor(int rootIdx, int num) {
        int cur = rootIdx;
        int ans = 0;
        for (int bit = MAX_LOG; bit >= 0; bit--) {
            int b = (num >> bit) & 1;
            // Prefer the same bit to minimize XOR
            if (tree[tree[cur].child[b]].cnt > 0) {
                cur = tree[cur].child[b];
            } else {
                ans |= (1 << bit);
                cur = tree[cur].child[b ^ 1];
            }
        }
        return ans;
    }

    // Get the root index of a specific version.
    int getRoot(int version) {
        return root[version];
    }

    // Add a new version by inserting a number.
    int addVersion(int num) {
        int newRoot = insert(root.back(), num);
        root.push_back(newRoot);
        versionCount++;
        return versionCount;
    }
};

// ===================================================================
// 2) Basic Operations: Insert and Query
//    These functions provide a simple interface for the most common
//    tasks: inserting numbers into the trie and querying for max/min XOR.
// ===================================================================

// 2.1) Insert a number into the trie and create a new version.
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - num: the integer to insert
//      Returns:
//        - the version number of the newly created version.
//      Time complexity: O(MAX_LOG)
//      Constraint: num must be representable within MAX_LOG bits.
//      Note: This is the primary way to build the trie.
int insertNumber(PersistentBinaryTrie<30>& trie, int num) {
    return trie.addVersion(num);
}

// 2.2) Query the maximum XOR of a number with any number in a given version.
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - version: the version to query (0-indexed)
//        - num: the number to XOR with
//      Returns:
//        - the maximum possible XOR value.
//      Time complexity: O(MAX_LOG)
//      Constraint: version must be a valid version number.
//      Note: This is used to answer queries like "what is the max XOR in a prefix".
int queryMaxXorInVersion(PersistentBinaryTrie<30>& trie, int version, int num) {
    return trie.queryMaxXor(trie.getRoot(version), num);
}

// 2.3) Query the minimum XOR of a number with any number in a given version.
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - version: the version to query (0-indexed)
//        - num: the number to XOR with
//      Returns:
//        - the minimum possible XOR value.
//      Time complexity: O(MAX_LOG)
//      Constraint: version must be a valid version number.
//      Note: This is useful for problems asking for the minimum XOR.
int queryMinXorInVersion(PersistentBinaryTrie<30>& trie, int version, int num) {
    return trie.queryMinXor(trie.getRoot(version), num);
}

// ===================================================================
// 3) Range Queries: Query on a subarray [L, R]
//    These functions use two versions to represent a range of indices.
//    The range is defined by versions L-1 and R.
// ===================================================================

// 3.1) Query the maximum XOR of a number with any number in a subarray [L, R].
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - L, R: the range of indices (1-indexed, inclusive)
//        - num: the number to XOR with
//      Returns:
//        - the maximum XOR value achievable with any element in a[L..R].
//      Time complexity: O(MAX_LOG)
//      Constraint: L <= R, and versions L-1 and R must exist.
//      Note: This is the most common use case for Persistent Trie.
//            It works by subtracting the counts of two versions.
int queryMaxXorInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num) {
    int rootR = trie.getRoot(R);
    int rootL = trie.getRoot(L - 1);
    // We traverse both roots simultaneously.
    // The difference in counts tells us if a path exists in the range.
    int curR = rootR, curL = rootL;
    int ans = 0;
    for (int bit = 30; bit >= 0; bit--) {
        int b = (num >> bit) & 1;
        int opposite = b ^ 1;
        // Check if the opposite child exists in the range
        if (trie.tree[trie.tree[curR].child[opposite]].cnt - trie.tree[trie.tree[curL].child[opposite]].cnt > 0) {
            ans |= (1 << bit);
            curR = trie.tree[curR].child[opposite];
            curL = trie.tree[curL].child[opposite];
        } else {
            curR = trie.tree[curR].child[b];
            curL = trie.tree[curL].child[b];
        }
    }
    return ans;
}

// 3.2) Query the minimum XOR of a number with any number in a subarray [L, R].
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - L, R: the range of indices (1-indexed, inclusive)
//        - num: the number to XOR with
//      Returns:
//        - the minimum XOR value achievable with any element in a[L..R].
//      Time complexity: O(MAX_LOG)
//      Constraint: L <= R, and versions L-1 and R must exist.
int queryMinXorInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num) {
    int rootR = trie.getRoot(R);
    int rootL = trie.getRoot(L - 1);
    int curR = rootR, curL = rootL;
    int ans = 0;
    for (int bit = 30; bit >= 0; bit--) {
        int b = (num >> bit) & 1;
        // Check if the same child exists in the range
        if (trie.tree[trie.tree[curR].child[b]].cnt - trie.tree[trie.tree[curL].child[b]].cnt > 0) {
            curR = trie.tree[curR].child[b];
            curL = trie.tree[curL].child[b];
        } else {
            ans |= (1 << bit);
            curR = trie.tree[curR].child[b ^ 1];
            curL = trie.tree[curL].child[b ^ 1];
        }
    }
    return ans;
}

// ===================================================================
// 4) Advanced Queries: K-th smallest XOR and Count of XORs < K
//    These functions extend the basic queries to handle ordering.
// ===================================================================

// 4.1) Find the K-th smallest XOR value (0-indexed) with 'num' in a range [L, R].
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - L, R: the range of indices (1-indexed, inclusive)
//        - num: the number to XOR with
//        - k: the 0-indexed order (e.g., k=0 gives the smallest XOR)
//      Returns:
//        - the K-th smallest XOR value.
//      Time complexity: O(MAX_LOG)
//      Constraint: k must be less than the number of elements in the range.
//      Note: This is useful for problems asking for the K-th best XOR.
int kthSmallestXorInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num, int k) {
    int rootR = trie.getRoot(R);
    int rootL = trie.getRoot(L - 1);
    int curR = rootR, curL = rootL;
    int ans = 0;
    for (int bit = 30; bit >= 0; bit--) {
        int b = (num >> bit) & 1;
        int cntSame = trie.tree[trie.tree[curR].child[b]].cnt - trie.tree[trie.tree[curL].child[b]].cnt;
        // If k is in the "same bit" subtree, go there. Otherwise, go to the opposite.
        if (k < cntSame) {
            curR = trie.tree[curR].child[b];
            curL = trie.tree[curL].child[b];
        } else {
            k -= cntSame;
            ans |= (1 << bit);
            curR = trie.tree[curR].child[b ^ 1];
            curL = trie.tree[curL].child[b ^ 1];
        }
    }
    return ans;
}

// 4.2) Count the number of XORs with 'num' that are strictly less than 'limit' in a range [L, R].
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - L, R: the range of indices (1-indexed, inclusive)
//        - num: the number to XOR with
//        - limit: the upper bound (exclusive)
//      Returns:
//        - the count of elements in a[L..R] such that (element XOR num) < limit.
//      Time complexity: O(MAX_LOG)
//      Constraint: limit >= 0.
//      Note: This is useful for problems involving counting pairs with XOR < K.
long long countXorLessThanInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num, int limit) {
    int rootR = trie.getRoot(R);
    int rootL = trie.getRoot(L - 1);
    int curR = rootR, curL = rootL;
    long long ans = 0;
    for (int bit = 30; bit >= 0; bit--) {
        if (curR == 0 && curL == 0) break;
        int b = (num >> bit) & 1;
        int limitBit = (limit >> bit) & 1;
        if (limitBit == 1) {
            // If limit's bit is 1, all numbers with the same bit as 'num' at this position
            // will produce an XOR with 0 at this bit, which is less than limit.
            // So we add their count and then continue with the opposite bit.
            ans += trie.tree[trie.tree[curR].child[b]].cnt - trie.tree[trie.tree[curL].child[b]].cnt;
            curR = trie.tree[curR].child[b ^ 1];
            curL = trie.tree[curL].child[b ^ 1];
        } else {
            // If limit's bit is 0, we must continue with the same bit to stay equal so far.
            curR = trie.tree[curR].child[b];
            curL = trie.tree[curL].child[b];
        }
    }
    return ans;
}

// ===================================================================
// 5) Tricks & Patterns that appeared in ECPC/ACPC
//    Extra useful utilities for specific problem types.
// ===================================================================

// 5.1) Solve "Maximum XOR Subarray" with range [L, R].
//      Problem: Given an array, answer queries of the form:
//      "Find max (a[p] xor a[p+1] xor ... xor a[R]) for L <= p <= R".
//      Parameters:
//        - prefixXor: an array where prefixXor[i] = a[1] xor ... xor a[i].
//        - L, R: the range (1-indexed, inclusive).
//        - x: an additional value to XOR with (often 0).
//      Returns:
//        - the maximum XOR value.
//      Time complexity: O(MAX_LOG) per query after building the trie.
//      Constraint: prefixXor must be built first, and a Persistent Trie
//                   must be constructed from prefixXor.
//      Note: The problem reduces to finding max (prefixXor[p-1] xor (prefixXor[R] xor x)).
//            So we query the range [L-1, R-1] for the best partner.
int maxSubarrayXorInRange(const vector<int>& prefixXor, PersistentBinaryTrie<30>& trie, int L, int R, int x = 0) {
    int target = prefixXor[R] ^ x;
    return queryMaxXorInRange(trie, L - 1, R - 1, target);
}

// 5.2) Build a Persistent Trie from an array of prefix XORs.
//      Parameters:
//        - arr: the original array (1-indexed, but can be 0-indexed).
//      Returns:
//        - a PersistentBinaryTrie object containing all prefix XORs.
//      Time complexity: O(n * MAX_LOG)
//      Constraint: arr elements must fit in MAX_LOG bits.
//      Note: This is a common setup for many XOR-related problems.
PersistentBinaryTrie<30> buildPersistentTrieFromArray(const vector<int>& arr) {
    PersistentBinaryTrie<30> trie;
    int currentXor = 0;
    trie.addVersion(currentXor); // version 0: empty, or prefix 0
    for (int x : arr) {
        currentXor ^= x;
        trie.addVersion(currentXor);
    }
    return trie;
}

// 5.3) Count pairs (i, j) with i < j and (a[i] xor a[j]) < K.
//      This is a classic problem; the implementation below shows how to
//      do it with a Persistent Trie by querying ranges for each i.
//      Parameters:
//        - arr: the input array.
//        - K: the upper bound (exclusive).
//      Returns:
//        - the number of pairs with XOR < K.
//      Time complexity: O(n * MAX_LOG)
//      Constraint: arr elements must fit in MAX_LOG bits.
//      Note: This is a placeholder; use the range version for actual counting.
long long countPairsWithXorLessThanK(const vector<int>& arr, int K) {
    // Not implemented directly; see countPairsWithXorLessThanKInRange.
    // Provided for completeness.
    return 0;
}

// 5.4) Count pairs (i, j) with L <= i < j <= R and (a[i] xor a[j]) < K.
//      This is a more general version of the above.
//      Parameters:
//        - prefixXor: the array of prefix XORs.
//        - L, R: the range of indices (1-indexed, inclusive).
//        - K: the upper bound (exclusive).
//      Returns:
//        - the number of pairs within [L, R] with XOR < K.
//      Time complexity: O((R-L+1) * MAX_LOG)
//      Constraint: prefixXor must be built.
//      Note: This is a more advanced version that uses range queries.
long long countPairsWithXorLessThanKInRange(const vector<int>& prefixXor, PersistentBinaryTrie<30>& trie, int L, int R, int K) {
    long long ans = 0;
    for (int i = L; i <= R; i++) {
        // For each element at position i, count previous elements in [L, i-1]
        // that give XOR < K with prefixXor[i].
        ans += countXorLessThanInRange(trie, L, i - 1, prefixXor[i], K);
    }
    return ans;
}

// 5.5) Find the maximum XOR of any two elements in a range [L, R].
//      Parameters:
//        - prefixXor: the array of prefix XORs.
//        - L, R: the range (1-indexed, inclusive).
//      Returns:
//        - the maximum XOR value between any two elements in a[L..R].
//      Time complexity: O((R-L+1) * MAX_LOG)
//      Constraint: prefixXor must be built.
//      Note: This is a more complex problem. For each i in [L, R], we query
//            the range [L, i-1] for the max XOR with a[i].
int maxXorPairInRange(const vector<int>& prefixXor, PersistentBinaryTrie<30>& trie, int L, int R) {
    int ans = 0;
    for (int i = L; i <= R; i++) {
        ans = max(ans, queryMaxXorInRange(trie, L, i - 1, prefixXor[i]));
    }
    return ans;
}

// ===================================================================
// 6) Helper Functions
// ===================================================================

// 6.1) Get the number of elements in a specific version.
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//        - version: the version number
//      Returns:
//        - the count of elements inserted up to that version.
//      Time complexity: O(1)
int getVersionSize(PersistentBinaryTrie<30>& trie, int version) {
    return trie.tree[trie.getRoot(version)].cnt;
}

// 6.2) Get the total number of versions created.
//      Parameters:
//        - trie: a PersistentBinaryTrie object
//      Returns:
//        - the number of versions (including version 0).
//      Time complexity: O(1)
int getVersionCount(PersistentBinaryTrie<30>& trie) {
    return trie.root.size();
}

// ===================================================================
// main() with example usage
// ===================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example 1: Basic Insert and Query
    PersistentBinaryTrie<30> trie;
    trie.addVersion(5);
    trie.addVersion(3);
    trie.addVersion(8);
    // Now versions: 0: empty, 1: [5], 2: [5,3], 3: [5,3,8]

    cout << "Max XOR of 7 in version 3: " << queryMaxXorInVersion(trie, 3, 7) << '\n'; // 15 (8^7=15)
    cout << "Min XOR of 7 in version 3: " << queryMinXorInVersion(trie, 3, 7) << '\n'; // 2 (5^7=2)

    // Example 2: Range Query
    cout << "Max XOR of 7 in range [2, 3] (elements 3 and 8): " << queryMaxXorInRange(trie, 2, 3, 7) << '\n'; // 15 (8^7=15)
    cout << "Min XOR of 7 in range [2, 3]: " << queryMinXorInRange(trie, 2, 3, 7) << '\n'; // 4 (3^7=4)

    // Example 3: K-th smallest XOR
    cout << "0-th smallest XOR of 7 in range [1, 3]: " << kthSmallestXorInRange(trie, 1, 3, 7, 0) << '\n'; // 2 (5^7=2)
    cout << "1-st smallest XOR of 7 in range [1, 3]: " << kthSmallestXorInRange(trie, 1, 3, 7, 1) << '\n'; // 4 (3^7=4)
    cout << "2-nd smallest XOR of 7 in range [1, 3]: " << kthSmallestXorInRange(trie, 1, 3, 7, 2) << '\n'; // 15 (8^7=15)

    // Example 4: Count XORs < K
    cout << "Count of XORs with 7 < 10 in range [1, 3]: " << countXorLessThanInRange(trie, 1, 3, 7, 10) << '\n'; // 2 (2 and 4)

    return 0;
}