Problem 57: Persistent Trie for K-th Smallest XOR Query

Problem Statement: Given an array of integers, construct a persistent trie to answer queries: for given indices L, R and an integer x, find the k-th smallest value of (a[i] XOR x) for L <= i <= R.

Input

The first line contains n and q. The next line contains n integers. Each of the next q lines contains four integers: L, R, x, and k.

Output

For each query, print the k-th smallest value of (a[i] XOR x) over i in [L, R]. If k is larger than number of elements, output -1.

Examples


Input:
5 2
1 2 3 4 5
1 3 2 2
2 5 1 3

Output:
1
4

Solution Explanation

The solution involves building a persistent trie where each version corresponds to the prefix of the array. Queries then find the k-th smallest XOR value by comparing the tries for prefix R and prefix L-1. This requires careful traversal at each bit level.

Solution in C++


#include 
using namespace std;

struct Node {
    int cnt;
    Node* left;
    Node* right;
    Node(): cnt(0), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int num, int bit = 31) {
    Node* newRoot = new Node();
    newRoot->cnt = (root ? root->cnt : 0) + 1;
    if(bit < 0) return newRoot;
    int b = (num >> bit) & 1;
    if(b == 0) {
        newRoot->right = (root ? root->right : nullptr);
        newRoot->left = insert(root ? root->left : nullptr, num, bit - 1);
    } else {
        newRoot->left = (root ? root->left : nullptr);
        newRoot->right = insert(root ? root->right : nullptr, num, bit - 1);
    }
    return newRoot;
}

int query(Node* R, Node* L, int x, int k, int bit = 31) {
    if(bit < 0) return 0;
    int b = (x >> bit) & 1;
    int cnt0 = 0;
    Node* R0 = (b == 0 ? R->left : R->right);
    Node* L0 = (L ? (b == 0 ? L->left : L->right) : nullptr);
    if(R0) cnt0 = R0->cnt - (L0 ? L0->cnt : 0);
    if(cnt0 >= k) {
        return query(R0, L0, x, k, bit - 1);
    } else {
        Node* R1 = (b == 0 ? R->right : R->left);
        Node* L1 = (L ? (b == 0 ? L->right : L->left) : nullptr);
        int res = query(R1, L1, x, k - cnt0, bit - 1);
        return (1 << bit) | res;
    }
}

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