Xor-Key-Hackerrank_Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int val[16];
class node{
    public:
    node* left;node* right;
    vector<int>s;
    node(node* l,node* r){
        left=l;right=r;
    }
};
class Trie{
    public:
    node* root=NULL;

    static void insert(node** temp,string &s,int pos,int k){
        if(pos==s.size()){
            (*temp)->s.push_back(k);
            return;
        }
        if(pos!=0)
        (*temp)->s.push_back(k);
        if(s[pos]=='0'){
            if((*temp)->left==NULL){
                (*temp)->left=new node(NULL,NULL);
            }
            insert(&((*temp)->left),s,pos+1,k);

        }else{
            if((*temp)->right==NULL){
                (*temp)->right=new node(NULL,NULL);
            }
            insert(&((*temp)->right),s,pos+1,k);
        }
    }
    void TrieInsert(string &s,int k){
        if(root==NULL){
            root=new node(NULL,NULL);
        }
        insert(&root,s,0,k);
    }
    bool isValid(node** temp,int l,int r){
        auto z=lower_bound((*temp)->s.begin(),(*temp)->s.end(),l);
        if(z!=(*temp)->s.end()){
            int x=*z;
            if(x<=r){
                return true;
            }
        }
        return false;
    }
    int TrieMaxi(node** temp,string &s,int pos,int l,int r){
         if(pos==s.size()){
             return 0;
         }
         if(s[pos]=='0'){
             if((*temp)->right!=NULL&&isValid(&((*temp)->right),l,r)){
                 return val[s.size()-1-pos]+TrieMaxi(&((*temp)->right),s,pos+1,l,r);
             }
             return TrieMaxi(&((*temp)->left),s,pos+1,l,r);

         }
         if((*temp)->left!=NULL&&isValid(&((*temp)->left),l,r)){
             return val[s.size()-1-pos]+TrieMaxi(&((*temp)->left),s,pos+1,l,r);
         }
         return TrieMaxi(&((*temp)->right),s,pos+1,l,r);
    }

    int getMyMaxi(string &s,int l,int r){
        return TrieMaxi(&root,s,0,l,r);
    }
};
int32_t main(){

    IOS
    val[0]=1;
    for(int i=1;i<16;i++){
        val[i]=val[i-1]*2;
    }
    int t;
    cin>>t;
    while(t--){
        int n;int q;
        cin>>n>>q;
        int x;
        Trie* myTrie = new Trie();
        for(int i=1;i<=n;i++){
            cin>>x;
            string temp;
            for(int j=0;j<16;j++){
                if(x&1){
                    temp.push_back('1');
                }else{
                    temp.push_back('0');
                }
                x/=2;
            }
            reverse(temp.begin(),temp.end());
            myTrie->TrieInsert(temp,i);

        }


        while(q--){
            int a,l,r;
            cin>>a>>l>>r;string temp;
            for(int i=0;i<16;i++){
                if(a&1){
                    temp.push_back('1');
                }else{
                    temp.push_back('0');
                }
                a/=2;
            }
            reverse(temp.begin(),temp.end());
            cout<<myTrie->getMyMaxi(temp,l,r)<<"\n";
        }








    }


    return 0;
}