You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith query.

&nbsp;
Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8


Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]


&nbsp;
Constraints:


	1 &lt;= arr.length, queries.length &lt;= 3 * 104
	1 &lt;= arr[i] &lt;= 109
	queries[i].length == 2
	0 &lt;= lefti &lt;= righti &lt; arr.length


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:


       """

       arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]

       find pref xor of arr

       pref = [x,x,x,x]

       for each query find the left and right indices
       the xor for range (l, r) would be pref[r] xor pref[l-1]
       
       """     
       n, m = len(queries), len(arr)

       answer = [1]*n

       pref = [1]*m
       pref[0] = arr[0]
       if m > 1:
           for i in range(1,m):
               pref[i] = pref[i-1] ^ arr[i]

       for (i, (l,r)) in enumerate(queries):
           if l == 0: answer[i] = pref[r]          
           else: answer[i] = pref[r] ^ pref[l-1]

       return answer
class Solution
{
    public int[] xorQueries(int[] arr, int[][] queries)
    {
        int[] ans = new int[queries.length];
        int[] xor = new int[arr.length];
        xor[0] = arr[0];
        // computing prefix XOR of arr
        for(int i = 1; i < arr.length; i++)
        {
            xor[i] = arr[i] ^ xor[i-1];
        }
        for(int i = 0; i < queries.length; i++)
        {
            // if query starts from something other than 0 (say i), then we XOR all values from arr[0] to arr[i-1]
            if(queries[i][0] != 0)
            {
                ans[i] = xor[queries[i][1]];
                for(int j = 0; j < queries[i][0]; j++)
                {
                    ans[i] = arr[j] ^ ans[i];
                }
            }
            // if start of query is 0, then we striaght up use the prefix XOR till ith element
            else
                ans[i] = xor[queries[i][1]];
        }
        return ans;
    }
}
class Solution {
public:
    
    // we know that (x ^ x)  = 0,
    
    // arr = [1,4,8,3,7,8],  let we have to calculate xor of subarray[2,4]
    
    // (1 ^ 4 ^ 8 ^ 3 ^ 7) ^ (1 ^ 4) = (8 ^ 3 ^ 7), this is nothing but prefix[right] ^ prefix[left - 1]
    
    // (1 ^ 1 = 0) and (4 ^ 4) = 0
    
    
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        
        int n = queries.size();
        
        // find the prefix xor of arr
        
        for(int i = 1; i < arr.size(); i++)
        {
            arr[i] = (arr[i - 1] ^ arr[i]);
        }
        
        // calculate each query
        
        vector<int> res(n);
        
        for(int i = 0; i < n; i++)
        {
            int left = queries[i][0];
            
            int right = queries[i][1];
            
            // find the xorr of the subarray
            
            int xorr = arr[right];
            
            if(left > 0)
            {
                xorr ^= arr[left - 1];
            }
            
            res[i] = xorr;
        }
       
        return res;
    }
};
var xorQueries = function(arr, queries) {
    let n = arr.length;
    
    while ((n & (n - 1)) != 0) {
        n++;
    }
    
    const len = n;
    const tree = new Array(len * 2).fill(0);
  
    build(tree, 1, 0, len - 1);
    
    const res = [];
    
    for (let i = 0; i < queries.length; i++) {
        const [start, end] = queries[i];
        
        const xor = query(tree, 1, 0, len - 1, start, end);
        
        res.push(xor);
    }
    
    
    return res;
    
   
    function build(tree, segmentIdx, segmentStart, segmentEnd) {
        if (segmentStart === segmentEnd) {
            tree[segmentIdx] = arr[segmentStart];
            return;
        }
        
        const mid = (segmentStart + segmentEnd) >> 1;
        build(tree, segmentIdx * 2, segmentStart, mid);
        build(tree, segmentIdx * 2 + 1, mid + 1, segmentEnd);
        
        tree[segmentIdx] = tree[segmentIdx * 2] ^ tree[segmentIdx * 2 + 1];
		return;
    } 
    
    
    function query(tree, node, nodeStart, nodeEnd, queryStart, queryEnd) {
        if (queryStart <= nodeStart && nodeEnd <= queryEnd) {
            return tree[node];
        }    
        if (nodeEnd < queryStart || queryEnd < nodeStart) {
            return 0;
        }
        
        const mid = (nodeStart + nodeEnd) >> 1;
        
        const leftXor = query(tree, node * 2, nodeStart, mid, queryStart, queryEnd);
        const rightXor = query(tree, node * 2 + 1, mid + 1, nodeEnd, queryStart, queryEnd);
        
        return leftXor ^ rightXor;
    }
};
``
XOR Queries of a Subarray