We have array of N (<=10^5) elements with Q(<=10^5) queries.Each query is of type: p q r s x, where we have to find if  there exist a element from array in range [p,q] and an element in  [r,s] whose xor is equal to X. If exists, print true else  false.Constraints:1 <= N <= 10^51 <= p,q,r,s <= N1 <= A[i] <= 10^5Example: Array : 1 2 3 4 5 6Query : 1 3 4 6 5 Output: true.1 from range [1,3] and 4 from range [4,6] has an XOR value equal to X=5.I tried to solve it by loading the second sub array into a hashmap then XORing x with each element from first array and if the result exists in hashmap answer is yes.But this \$O(n)\$ solution for each query isn't sufficient to pass. I am looking for ideas for how I can achieve this in possible \$O(logn)\$ or \$O(1\$) time for each query, or if it is possible to answer queries offline using MO's algorithm in \$O(sqrt(n))\$ time.#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef vector<int> vi;int a[100001];bool query(int p,int q,int r,int s,int x){    unordered_map<int,int> mp;    for(int i =r;i<=s;i++)    {        mp[a[i]]=1;    }    for(int i =p;i<=q;i++)    {        if(mp.count(a[i]^x) > 0)        {            return true;        }    }    return false;}int main(){    int n,q;    cin>>n>>q;    for(int i =0;i<n;i++)    {        cin>>a[i];    }    while(q--)    {        int p,q,r,s,x;        cin>>p>>q>>r>>s>>x;        // -1 because they are 1-indexed        if(query(p-1,q-1,r-1,s-1,x))        {            cout<<true\n;        }        else        {            cout<<false\n;        }    }    return 0;}
Given an array of N elements, answer Q queries asking if there exist two elements from two specified range with a given XOR value
c++