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

// ===================================================================
// This file contains a collection of Binary Trie (Bitwise Trie)
// algorithms. A Binary Trie is a tree where each node has up to two
// children (0 and 1), representing the binary bits of integers, from
// the most significant bit (MSB) down to the least significant bit.
// It is used to efficiently answer queries about XOR, maximum XOR,
// minimum XOR, and counting numbers with XOR constraints.
//
// 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
// ===================================================================

// ===================================================================
// SECTION 1: Basic Binary Trie Node and Helpers
// ===================================================================

// LOG is the highest bit index we care about.
// For 32‑bit signed integers (up to 2^31‑1), bits 30..0 are enough.
// If you use long long (up to 9e18), change LOG to 60.
// IMPORTANT: Set LOG according to the maximum value you will insert.
static const int LOG = 30;   // bits from LOG down to 0 inclusive

// A node in the Binary Trie.
struct TrieNode {
    int child[2];   // child[0] for bit 0, child[1] for bit 1
    int cnt;        // how many numbers pass through this node (for counting / deletion)
    TrieNode() {
        child[0] = child[1] = -1;
        cnt = 0;
    }
};

// ===================================================================
// SECTION 2: Basic Binary Trie Class
// ===================================================================

// This class provides the core trie operations.
// It stores integers and supports:
//   - insert(x)
//   - erase(x)   (decrement counts, assumes x exists)
//   - maxXor(x)  : maximum XOR value with any stored number
//   - minXor(x)  : minimum XOR value with any stored number
//   - countXorLessThan(x, limit) : how many stored numbers y satisfy (x XOR y) < limit
class BinaryTrie {
public:
    vector<TrieNode> tr;
    
    BinaryTrie() {
        tr.push_back(TrieNode());   // node 0 is the root
    }

    // Insert a number x into the trie.
    // Time: O(LOG)
    void insert(int x) {
        int node = 0;
        tr[0].cnt++;                // increment root count
        for (int bit = LOG; bit >= 0; bit--) {
            int b = (x >> bit) & 1;
            if (tr[node].child[b] == -1) {
                tr[node].child[b] = tr.size();
                tr.push_back(TrieNode());
            }
            node = tr[node].child[b];
            tr[node].cnt++;
        }
    }

    // Erase one occurrence of x from the trie.
    // Precondition: x has been inserted at least once.
    // Time: O(LOG)
    void erase(int x) {
        int node = 0;
        tr[0].cnt--;                // decrement root count
        for (int bit = LOG; bit >= 0; bit--) {
            int b = (x >> bit) & 1;
            int nxt = tr[node].child[b];
            tr[nxt].cnt--;
            node = nxt;
        }
    }

    // Return the maximum possible XOR value between x and any number
    // currently stored in the trie.
    // If the trie is empty, the behaviour is undefined (will return 0).
    // Time: O(LOG)
    int maxXor(int x) {
        int node = 0;
        int ans = 0;
        for (int bit = LOG; bit >= 0; bit--) {
            int b = (x >> bit) & 1;
            int want = b ^ 1;   // we prefer the opposite bit to get 1 in XOR
            if (tr[node].child[want] != -1 && tr[tr[node].child[want]].cnt > 0) {
                ans |= (1 << bit);
                node = tr[node].child[want];
            } else {
                node = tr[node].child[b];
            }
        }
        return ans;
    }

    // Return the minimum possible XOR value between x and any number
    // stored in the trie.
    // If the trie is empty, returns INT_MAX (you should check emptiness).
    // Time: O(LOG)
    int minXor(int x) {
        int node = 0;
        int ans = 0;
        for (int bit = LOG; bit >= 0; bit--) {
            int b = (x >> bit) & 1;
            // try to go with the same bit to get 0 in XOR first
            if (tr[node].child[b] != -1 && tr[tr[node].child[b]].cnt > 0) {
                node = tr[node].child[b];
            } else {
                ans |= (1 << bit);
                node = tr[node].child[b ^ 1];
            }
        }
        return ans;
    }

    // Count how many numbers y currently in the trie satisfy (x XOR y) < limit.
    // This is useful for counting pairs/subarrays with XOR less than a threshold.
    // If limit <= 0, returns 0. If limit is very large, returns total count.
    // Time: O(LOG)
    int countXorLessThan(int x, int limit) {
        if (limit <= 0) return 0;
        int node = 0;
        int ans = 0;
        for (int bit = LOG; bit >= 0; bit--) {
            if (node == -1 || tr[node].cnt == 0) break;
            int xb = (x >> bit) & 1;
            int lb = (limit >> bit) & 1;
            // If limit has bit 1 at this position, we can take the branch
            // that makes XOR bit 0 (less at this bit), and add its count.
            if (lb == 1) {
                int take0 = tr[node].child[xb]; // XOR bit = 0
                if (take0 != -1 && tr[take0].cnt > 0) {
                    ans += tr[take0].cnt;
                }
                // then continue with the branch that makes XOR bit = 1
                node = tr[node].child[xb ^ 1];
            } else {
                // limit bit is 0, we must have XOR bit 0 to stay less
                node = tr[node].child[xb];
            }
        }
        // At the end, if we exactly followed limit bits with XOR = 0 all the way,
        // then (x XOR y) == limit, not less, so we don't add.
        return ans;
    }

    // Count how many numbers y satisfy (x XOR y) <= limit.
    // Simply call countXorLessThan(x, limit+1) (careful with overflow).
    int countXorLessEqual(int x, int limit) {
        if (limit == INT_MAX) return totalCount(); // avoid overflow
        return countXorLessThan(x, limit + 1);
    }

    // Return the total number of elements currently stored.
    int totalCount() {
        return tr[0].cnt;
    }
};

// ===================================================================
// SECTION 3: Common Queries on Arrays using Binary Trie
// ===================================================================

// 3.1) Maximum XOR of any two numbers in the array.
//      Parameters:
//        - arr: vector of integers (can be unsorted, any values)
//      Returns:
//        - the maximum XOR value between any pair (i != j) in arr.
//      Time complexity: O(n * LOG) where n = arr.size()
//      Constraint: arr must have at least 2 elements.
int maxXorPair(vector<int>& arr) {
    BinaryTrie trie;
    trie.insert(arr[0]);
    int ans = 0;
    for (int i = 1; i < (int)arr.size(); i++) {
        ans = max(ans, trie.maxXor(arr[i]));
        trie.insert(arr[i]);
    }
    return ans;
}

// 3.2) Minimum XOR of any two numbers in the array (minimum pair XOR).
//      Parameters:
//        - arr: vector of integers
//      Returns:
//        - the minimum XOR value between any pair (i != j).
//      Time complexity: O(n * LOG)
//      Constraint: arr must have at least 2 elements.
//      NOTE: An easier method is to sort the array, the minimum XOR pair
//            will be between adjacent elements after sorting. This trie
//            method works too but is slower (though still O(n LOG)).
int minXorPair(vector<int>& arr) {
    BinaryTrie trie;
    trie.insert(arr[0]);
    int ans = INT_MAX;
    for (int i = 1; i < (int)arr.size(); i++) {
        ans = min(ans, trie.minXor(arr[i]));
        trie.insert(arr[i]);
    }
    return ans;
}

// 3.3) Count the number of pairs (i < j) such that (arr[i] XOR arr[j]) < K.
//      Parameters:
//        - arr: vector of integers
//        - K: threshold (non-negative)
//      Returns:
//        - total number of unordered pairs with XOR < K.
//      Time complexity: O(n * LOG)
//      Constraint: K >= 0. If K == 0, answer is 0.
long long countPairsXorLessThan(vector<int>& arr, int K) {
    if (K <= 0) return 0;
    BinaryTrie trie;
    long long ans = 0;
    for (int x : arr) {
        ans += trie.countXorLessThan(x, K);
        trie.insert(x);
    }
    return ans;
}

// 3.4) Count the number of subarrays whose XOR is < K.
//      We use prefix XOR: pref[i] = XOR of arr[0..i-1].
//      A subarray XOR = pref[r] XOR pref[l-1].
//      So we insert each prefix into a trie and count how many previous
//      prefixes give XOR < K with the current prefix.
//      Parameters:
//        - arr: vector of integers
//        - K: threshold (non-negative)
//      Returns:
//        - number of contiguous subarrays with XOR < K.
//      Time complexity: O(n * LOG)
//      Constraint: K >= 0. If K == 0, answer is 0 because XOR of empty? no.
long long countSubarraysXorLessThan(vector<int>& arr, int K) {
    if (K <= 0) return 0;
    BinaryTrie trie;
    trie.insert(0); // prefix 0 for empty subarray
    long long ans = 0;
    int pref = 0;
    for (int x : arr) {
        pref ^= x;
        ans += trie.countXorLessThan(pref, K);
        trie.insert(pref);
    }
    return ans;
}

// 3.5) Maximum XOR of any subarray.
//      Equivalent to maximum difference between two prefix XORs.
//      We insert prefix XORs and query maxXor for each prefix.
//      Parameters:
//        - arr: vector of integers
//      Returns:
//        - the maximum XOR value of any subarray.
//      Time complexity: O(n * LOG)
//      Constraint: arr non-empty.
int maxSubarrayXor(vector<int>& arr) {
    BinaryTrie trie;
    trie.insert(0);
    int pref = 0, ans = 0;
    for (int x : arr) {
        pref ^= x;
        ans = max(ans, trie.maxXor(pref));
        trie.insert(pref);
    }
    return ans;
}

// ===================================================================
// SECTION 4: Sliding Window Binary Trie (with insert/delete)
// ===================================================================

// This class extends the basic trie with the ability to erase elements
// (already present in BinaryTrie). You can use it in a two-pointer
// / sliding window scenario where you add numbers to the right and
// remove from the left while maintaining the trie.
//
// Example: Count subarrays with XOR <= K in O(n LOG) using two pointers?
// But careful: sliding window with XOR does NOT work with monotonicity
// because XOR is not monotonic. However, if the problem involves AND/OR,
// but for XOR we use prefix + trie. Still, this insert/erase trie can
// be used for other constraints like "maximum XOR of subarray with
// length at most L" etc.

// The BinaryTrie class already has erase() and insert().
// So no additional class is needed; just use BinaryTrie and call erase.

// ===================================================================
// SECTION 5: Persistent Binary Trie (for range queries)
// ===================================================================

// A Persistent Binary Trie allows you to query maximum XOR with x using
// only prefix XORs that lie inside an index range [L, R].
// This is useful when you have an array and many queries asking:
// "Given L, R, and x, find max XOR of x with any element in arr[L..R]".
//
// We build a persistent trie over the array elements (or prefix XORs).
// Each version corresponds to inserting one more element.
// To query range [L, R], we use version R and version L-1 and subtract counts.
//
// NOTE: This is an advanced data structure. Use only when needed.
// The code below is a simplified implementation for integers with LOG bits.

struct PersistentNode {
    int child[2];
    int cnt;
    PersistentNode() {
        child[0] = child[1] = -1;
        cnt = 0;
    }
};

class PersistentBinaryTrie {
public:
    vector<PersistentNode> tr;
    vector<int> root; // root[i] = node index after inserting first i elements

    PersistentBinaryTrie() {
        tr.push_back(PersistentNode()); // node 0 is null/empty
        root.push_back(0);
    }

    // Insert value x into the trie and return the new root node index.
    // This creates a new version without modifying previous nodes.
    int insert(int prevRoot, int x) {
        int newRoot = tr.size();
        tr.push_back(tr[prevRoot]);
        tr[newRoot].cnt++;
        int curNew = newRoot;
        int curPrev = prevRoot;
        for (int bit = LOG; bit >= 0; bit--) {
            int b = (x >> bit) & 1;
            // copy the previous node's child pointers
            int prevChild = (curPrev == -1) ? -1 : tr[curPrev].child[b];
            int newChild = tr.size();
            tr.push_back(PersistentNode());
            if (prevChild != -1) {
                tr[newChild] = tr[prevChild];
            }
            tr[newChild].cnt++;
            tr[curNew].child[b] = newChild;
            curNew = newChild;
            curPrev = prevChild;
        }
        return newRoot;
    }

    // Build persistent trie from an array of values.
    // The values can be prefix XORs or elements.
    void build(const vector<int>& vals) {
        for (int v : vals) {
            int newRoot = insert(root.back(), v);
            root.push_back(newRoot);
        }
    }

    // Query maximum XOR with x using only values inserted in versions
    // (lRoot .. rRoot] i.e. indices [l, r) in the original array.
    // Here lRoot = root[l], rRoot = root[r] (root is 1-indexed in build).
    // If you use build on prefix array pref[0..n], then query(l, r, x)
    // where l and r are prefix indices (l < r) uses pref[l..r-1].
    int queryRangeMaxXor(int lRoot, int rRoot, int x) {
        int ans = 0;
        int nodeL = lRoot, nodeR = rRoot;
        for (int bit = LOG; bit >= 0; bit--) {
            int b = (x >> bit) & 1;
            int want = b ^ 1;
            int cntWant = 0;
            if (tr[nodeR].child[want] != -1) {
                cntWant = tr[tr[nodeR].child[want]].cnt;
            }
            if (tr[nodeL].child[want] != -1) {
                cntWant -= tr[tr[nodeL].child[want]].cnt;
            }
            if (cntWant > 0) {
                ans |= (1 << bit);
                nodeR = tr[nodeR].child[want];
                nodeL = tr[nodeL].child[want];
            } else {
                nodeR = tr[nodeR].child[b];
                nodeL = tr[nodeL].child[b];
            }
        }
        return ans;
    }
};

// Example of using Persistent Trie for range maximum XOR queries.
// Suppose you have an array arr and you need to answer q queries:
// For each query (l, r, x) 1-indexed inclusive, find max XOR of x
// with any arr[i] where l <= i <= r.
// You can build persistent trie on arr (1-indexed) and call queryRangeMaxXor(root[l-1], root[r], x).

// ===================================================================
// SECTION 6: Common Tricks and Notes from ECPC/ACPC
// ===================================================================

// Trick 1: Maximum XOR of two numbers can also be solved by sorting?
//          No, Trie is the standard.

// Trick 2: Counting subarrays with XOR in [L, R] can be done by
//          countSubarraysXorLessThan(R+1) - countSubarraysXorLessThan(L)
//          using the same trie function (be careful with L=0).
//          So you can implement:
long long countSubarraysXorInRange(vector<int>& arr, int L, int R) {
    if (L > R) return 0;
    if (L == 0) {
        return countSubarraysXorLessThan(arr, R+1);
    }
    return countSubarraysXorLessThan(arr, R+1) - countSubarraysXorLessThan(arr, L);
}

// Trick 3: If you need to count pairs (i, j) with XOR >= K, use total pairs - countPairsXorLessThan(arr, K).
//          total pairs = n*(n-1)/2.
long long countPairsXorGreaterEqual(vector<int>& arr, int K) {
    long long n = arr.size();
    long long total = n * (n - 1) / 2;
    return total - countPairsXorLessThan(arr, K);
}

// ===================================================================
// Additional functions for Binary Trie tricks and utilities
// ===================================================================

// ===================================================================
// Trick 4 (alternative): Minimum XOR pair using sorting (simpler, O(n log n))
// ===================================================================

// 4.1) Minimum XOR of any two numbers in the array using sorting.
//      Parameters:
//        - arr: vector of integers
//      Returns:
//        - the minimum XOR value between any pair (i != j).
//      Time complexity: O(n log n)
//      Constraint: arr must have at least 2 elements.
//      Note: This is simpler than the trie approach and works for static arrays.
//            Sorting adjacent elements works because the minimum XOR pair
//            will always be adjacent after sorting (proof: for any three
//            numbers a < b < c, min(a^b, b^c) <= a^c).
int minXorPairUsingSorting(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    int ans = INT_MAX;
    for (int i = 1; i < (int)arr.size(); i++) {
        ans = min(ans, arr[i] ^ arr[i-1]);
    }
    return ans;
}

// ===================================================================
// Trick 7: Maximum XOR between any element from array A and any element from array B
// ===================================================================

// 7.1) Given two arrays A and B, find the maximum value of (a XOR b)
//      where a ∈ A and b ∈ B.
//      Parameters:
//        - A, B: vectors of integers
//      Returns:
//        - the maximum XOR value between any a in A and b in B.
//      Time complexity: O((n+m) * LOG) where n = A.size(), m = B.size()
//      Constraint: both arrays non-empty.
//      Note: We insert all elements of A into a trie, then for each b in B
//            query the maximum XOR.
int maxXorFromTwoArrays(const vector<int>& A, const vector<int>& B) {
    BinaryTrie trie;
    for (int a : A) trie.insert(a);
    int ans = 0;
    for (int b : B) {
        ans = max(ans, trie.maxXor(b));
    }
    return ans;
}

// ===================================================================
// Trick 5: "MUBIS" – common ECPC problems: Maximum XOR Subarray or Minimum XOR Pair
//          The functions maxSubarrayXor and minXorPair (and maxXorPair)
//          are already provided in the main template. They cover these.
// ===================================================================

// ===================================================================
// Trick 6: Using erase() for sliding window / dynamic sets
//          The BinaryTrie class already supports erase() by decreasing cnt.
//          Below is an example of how to use it to count pairs (i, j)
//          within a window [L, R] that satisfy (arr[i] XOR arr[j]) < K.
//          However, since XOR is not monotonic, a sliding window is not
//          usually used for counting subarrays with XOR < K (prefix trie is better).
//          But this example demonstrates the use of insert/erase for dynamic
//          sets in general, which can be applied to other bitwise operations
//          (like AND/OR) where monotonicity holds.
// ===================================================================

// This function is just an example; it counts the number of pairs (i, j)
// with L <= i < j <= R such that (arr[i] XOR arr[j]) < K.
// It uses a trie that is updated as the window slides.
// Parameters:
//   - arr: the array
//   - L, R: inclusive indices of the window
//   - K: threshold
// Returns:
//   - number of pairs in that window with XOR < K.
// Time complexity: O((R-L+1) * LOG)
long long countPairsXorLessThanInWindow(const vector<int>& arr, int L, int R, int K) {
    if (K <= 0 || L >= R) return 0;
    BinaryTrie trie;
    long long ans = 0;
    // Insert elements from L to R one by one and count pairs
    for (int i = L; i <= R; i++) {
        ans += trie.countXorLessThan(arr[i], K);
        trie.insert(arr[i]);
    }
    return ans;
}

// Example of sliding window with insert/erase (maintaining a window of fixed size):
// Suppose we want to answer many queries (L, R) quickly, we can precompute?
// Not needed here; the above function just shows usage.

// ===================================================================
// Utility: Build a trie from a vector (convenience function)
// ===================================================================

// This function builds a BinaryTrie from a vector of integers.
// Parameters:
//   - vals: vector of integers
// Returns:
//   - a BinaryTrie object containing all values.
BinaryTrie buildTrieFromVector(const vector<int>& vals) {
    BinaryTrie trie;
    for (int x : vals) trie.insert(x);
    return trie;
}

// ===================================================================
// Additional: Count of numbers in trie that are <= x (not directly XOR)
// Not common, but useful for some bitwise problems.
// The BinaryTrie can be extended to count numbers less than x.
// ===================================================================

// This function counts how many numbers stored in the trie are strictly less than x.
// Parameters:
//   - x: threshold
// Returns:
//   - count of stored numbers y such that y < x.
// Time complexity: O(LOG)
// Note: This works because we store bits from MSB to LSB, and we can traverse
//       to count numbers less than x.
//       This is not a typical XOR query but can be used in combination.
int countLessThanInTrie(BinaryTrie& trie, int x) {
    int node = 0;
    int ans = 0;
    for (int bit = LOG; bit >= 0; bit--) {
        if (node == -1 || trie.tr[node].cnt == 0) break;
        int xb = (x >> bit) & 1;
        if (xb == 1) {
            // add count of numbers with bit 0 at this position (they are smaller)
            int zeroChild = trie.tr[node].child[0];
            if (zeroChild != -1) ans += trie.tr[zeroChild].cnt;
            // then continue with bit 1 to match x
            node = trie.tr[node].child[1];
        } else {
            // xb == 0, we must continue with bit 0 to stay less or equal
            node = trie.tr[node].child[0];
        }
    }
    // At the end, if we followed exactly x, we didn't count it (strictly less)
    return ans;
}

// ===================================================================
// Another utility: Count numbers in trie with XOR in range [L, R]
// ===================================================================

// Count how many stored numbers y satisfy L <= (x XOR y) <= R.
// This can be done using countXorLessThan twice.
int countXorInRange(BinaryTrie& trie, int x, int L, int R) {
    if (L > R) return 0;
    int right = trie.countXorLessThan(x, R+1);
    int left = trie.countXorLessThan(x, L);
    return right - left;
}

// ===================================================================
// New section: Advanced - Maximum XOR of subarray with length at most K
// ===================================================================

// Problem: Given an array arr, find the maximum XOR of any subarray
// whose length is at most K (or exactly K, etc.)
// Using prefix XOR and a trie that supports deletion to maintain only
// prefixes that are within the last K positions.
// Parameters:
//   - arr: vector of integers
//   - K: maximum length of subarray (K >= 1)
// Returns:
//   - maximum XOR of any subarray of length <= K.
// Time complexity: O(n * LOG)
// Constraint: K >= 1.
int maxSubarrayXorAtMostK(const vector<int>& arr, int K) {
    int n = arr.size();
    if (n == 0) return 0;
    BinaryTrie trie;
    trie.insert(0); // prefix 0
    int pref = 0;
    int ans = 0;
    // We'll keep a queue of prefix values to remove those that fall out of the window.
    queue<int> prefixes; // store prefix values in order
    prefixes.push(0);
    
    for (int i = 0; i < n; i++) {
        pref ^= arr[i];
        // insert current prefix
        trie.insert(pref);
        prefixes.push(pref);
        
        // If window size exceeds K, remove the oldest prefix
        if ((int)prefixes.size() > K + 1) { // because we have prefix for each position
            int old = prefixes.front();
            prefixes.pop();
            trie.erase(old);
        }
        
        // Query max XOR with current prefix
        ans = max(ans, trie.maxXor(pref));
    }
    return ans;
}

// ===================================================================
// End of additions
// ===================================================================

// ===================================================================
// SECTION 7: Utility function: build from vector and standard queries
// ===================================================================

// The BinaryTrie class is dynamic and you can insert any number of elements.
// The PersistentBinaryTrie is for static arrays with many range queries.

// ===================================================================
// main() – Example usage (can be ignored)
// ===================================================================

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

    // Example 1: max XOR pair
    vector<int> arr = {3, 10, 5, 25, 2, 8};
    cout << "Max XOR pair = " << maxXorPair(arr) << "\n"; // 28 (5^25)

    // Example 2: count subarrays with XOR < 10
    vector<int> nums = {1, 2, 3, 4};
    cout << "Subarrays XOR < 10: " << countSubarraysXorLessThan(nums, 10) << "\n";

    // Example 3: Persistent trie range query
    vector<int> vals = {1, 2, 3, 4};
    PersistentBinaryTrie pTrie;
    pTrie.build(vals); // builds versions for prefix elements
    // query max XOR with x=5 among values in range [1,3] (1-indexed)
    int l = 1, r = 3, x = 5;
    int ans = pTrie.queryRangeMaxXor(pTrie.root[l-1], pTrie.root[r], x);
    cout << "Max XOR in range [1,3] with 5 = " << ans << "\n";

    return 0;
}