Given the array arr of positive integers and the array queries where queries[i] = [Li, Ri], for each query i compute the XOR of elements from Li to Ri (that is, arr[Li] xor arr[Li+1] xor ... xor arr[Ri] ). Return an array containing the result for the given queries.
 
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]

 
Constraints:

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

Difficulty: interview

Starter code:

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

Solutions:
from itertools import accumulate
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xors = [0]
        for a in arr:
            xors.append(a^xors[-1])
        return [xors[i]^xors[j+1] for i,j in queries]
    



'''
x ^ y = z

0 ^ 1 = 1
1 ^ 0 = 1
0 ^ 0 = 0
1 ^ 1 = 0

逆推：
z   y   x
1   1 = 0
1   0 = 1
0   0 = 0
0   1 = 1

可见，仍是异或。计算前缀即可
'''

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        prefix_xor = [0] * n
        prefix_xor[0] = arr[0]
        for i in range(1, n):
            prefix_xor[i] = prefix_xor[i - 1] ^ arr[i]
        ret = []
        for start, end in queries:
            if start == 0:
                ret.append(prefix_xor[end])
            else:
                ret.append(prefix_xor[start - 1] ^ prefix_xor[end])
        return ret


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        
        prefix = []
        curr = 0
        for n in arr:
            curr ^= n
            prefix.append(curr)
            
        res = []
        for l, r in queries:
            if l == 0:
                res.append(prefix[r])
            else:
                res.append(prefix[r] ^ prefix[l-1])
        return res

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        result =[]
        prefixArr = [0] * len(arr)
        prefixArr[0] = arr[0]
        for i in range(1, len(arr)):
            prefixArr[i] = prefixArr[i-1] ^ arr[i]
        
        for j in range(len(queries)):
            start = queries[j][0]
            end = queries[j][1]
            
            if start == 0: result.append(prefixArr[end])
            else: result.append(prefixArr[start - 1] ^ prefixArr[end] )
        
        return result     


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        lx=[arr[0]]
        for i in range(1,len(arr)):
            lx.append(lx[i-1]^arr[i])
        return([lx[i[1]] if i[0]==0 else (lx[i[0]-1]^lx[i[1]]) for i in queries])
    
    
#         for i in queries:
#             if i[0]==0:
#                 ls.append(lx[i[1]])
#             else:
#                 ls.append(lx[i[0]-1]^lx[i[1]])
                
        # return ls


class Solution:
    def xorQueries(self, A: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(len(A) - 1):
            A[i + 1] ^= A[i]
        return [A[j] ^ A[i - 1] if i else A[j] for i, j in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        dp=[0]*len(arr)
        dp[0] = arr[0]
        for i in range(1,len(arr)):
            dp[i] = dp[i-1]^arr[i]
        #print(dp)   
        res = []
        for i in range(len(queries)):
            
            if queries[i][0]>0:
                res.append(dp[queries[i][0]-1]^dp[queries[i][1]])
            else:
                res.append(dp[queries[i][1]])
                
        return res
            
            
            


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(1, len(arr)):
            arr[i] ^= arr[i - 1]
        result = []
        for x, y in queries:
            if x == 0:
                result.append(arr[y])
            else:
                result.append(arr[y] ^ arr[x - 1])
        return result


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        prefix_sum = [arr[0]]
        
        for i in range(1, len(arr)):
            prefix_sum.append(prefix_sum[-1] ^ arr[i])
        
        result = []
        
        for l, r in queries:
            result.append(prefix_sum[r])
            if l > 0:
                result[-1] ^= prefix_sum[l - 1]
        
        return result

class Solution:
#     def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
#         ans = []
#         pool = dict()
#         for r in queries:
#             if tuple(r) in pool:
#                 ans.append(pool[tuple(r)])
#             else:
#                 pool[tuple(r)] = reduce(lambda x,y: x^y, arr[r[0]:r[1]+1])
#                 ans.append(pool[tuple(r)])
#         return ans
    
    # fact: xor[i,j] = xor[0,i] ^ xor[0,j]
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        ans = []
        # prefix the arr
        for i in range(1, len(arr)):
            arr[i] ^= arr[i-1]
        return [arr[j] ^ arr[i-1] if i > 0 else arr[j] for i, j in queries]


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        if len(arr)==1:
            return [arr[0] for i in queries]
        
        table = [arr[0]]*len(arr)
        for i in range(1,len(arr)):
            table[i] = table[i-1] ^ arr[i] 
        '''
        print(table)
        print(arr[0])
        print(arr[0]^arr[1])
        print(arr[0]^arr[1]^arr[2])
        print(arr[0]^arr[1]^arr[2]^arr[3
        '''
        
        '''
        table = [out]*len(arr)
        for i in range(1,len(arr)):
            for j in range(i,len(arr)):
                table[i][j] = table[i-1][j] ^ arr[j]
        '''
        out = [0]*len(queries)
        for i,(l,r) in enumerate(queries):
            #print(f'i:{i}, l:{l}, r:{r}')
            if l>0:
                out[i] = table[l-1] ^ table[r] 
            else:
                out[i] = table[r]
            
        return out

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xorarr = [0]
        for n in arr:
            xorarr.append(xorarr[-1]^n)
        
        res = []
        for i, j in queries:
            res.append(xorarr[j+1]^xorarr[i])
        
        return res

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xors = [arr[0]]
        
        n = len(arr)
        for i in range(1, n):
            xors.append(xors[-1] ^ arr[i])
        
        res = []
        for query in queries:
            l, r = query
            temp = xors[r]
            if l != 0:
                temp ^= xors[l - 1]
            res.append(temp)
        
        return res


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xors = []
        xoraccum = 0
        for n in arr:
            xoraccum^=n
            xors.append(xoraccum)
        ret = []
        for query in queries:
            l, r = query[0], query[1]
            rxor = xors[r]
            lxor = 0 if l == 0 else xors[l-1]
            ret.append(rxor^lxor)
        return ret

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        a=0;n=len(arr)
        for i in range(n):
            a^=arr[i]
            arr[i]=a
        ans=[]
        for i,j in queries:
            if i==0:

                ans.append(arr[j])
            else:
                ans.append(arr[j]^arr[i-1])
        return ans


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        x = 0
        xors = []
        for i in arr:
            x ^= i
            xors.append(x)
        return [xors[i[1]]^xors[i[0]]^arr[i[0]] for i in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        if len(arr) == 0:
            return []
        
        xor_arr = [0 for i in range(len(arr))]
        for index, v in enumerate(arr):
            if index == 0:
                xor_arr[index] = arr[index]
            else:
                xor_arr[index] = xor_arr[index - 1] ^ arr[index]
        results = [0 for i in range(len(queries))]
        for index, query in enumerate(queries):
            start = query[0]
            end = query[1]
            if start == 0:
                results[index] = xor_arr[end]
            else:
                results[index] = xor_arr[end] ^ xor_arr[start - 1]
        return results

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(len(arr)-1):
            arr[i+1] ^= arr[i]
        
        res = []
        for i,j in queries:
            if i == 0:
                res.append(arr[j])
            else:
                res.append(arr[i-1]^arr[j])
        return res


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        #use extra array to store the information
        prefix=[0]*len(arr)
        prefix[0]=arr[0]
        for i in range(1,len(arr)):
            prefix[i]=prefix[i-1]^arr[i]
        ans=[]
        for query in queries:
            start=query[0]
            end=query[1]
            if start==0:
                ans.append(prefix[end])
            else:
                ans.append(prefix[start-1]^prefix[end])
                
        return ans

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        n = len(arr)
        prefix = [0 for _ in range(n+1)]
        for i in range(n):
                prefix[i+1] = prefix[i]^arr[i]
        res = []
        print(prefix)
        for l, r in queries:
                print((l, r))
                res.append(prefix[r+1]^prefix[l])
                
        return res


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        cumArr = []
        resultArr = []
        for index in range(len(arr)):
            if(index == 0):
                cumArr.insert(index,arr[index])
            else:
                cumArr.insert(index,arr[index]^cumArr[index-1])
        for query in queries:
            left = query[0]
            right = query[1]    
            if(left is not 0):
                resultArr.append(cumArr[right]^cumArr[left-1])
            else:
                resultArr.append(cumArr[right])
        return resultArr        

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        ans = []
        
        
        prefix=[0]*n
        prefix[0] = arr[0]
        
        for i in range(1,n):
            
            prefix[i] = prefix[i-1]^arr[i]
        for q in queries:
            l,r = q
            if l==0:
                ans.append(prefix[r])
            else:
                ans.append(prefix[r]^prefix[l-1])
        return ans
        


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        
        n = len(arr)
        precompute = []
        
        xor = 0
        for num in arr:
            xor ^= num
            precompute.append(xor)
        
        ans = []
        for s, e in queries:
            if s == 0:
                ans += [precompute[e]]
            else:
                ans += [precompute[e] ^ precompute[s-1]]
        
        return ans


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        prefix = [arr[0]]
        for i in range(1,len(arr)):
            prefix.append(prefix[-1]^arr[i])
        result = []
        for s,e in queries:
            if s == 0:
                result.append(prefix[e])
            else:
                result.append(prefix[e]^prefix[s-1])
        return result

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
            xored = [None] * len(arr)
            ans = [None] * len(queries)

            # construct the array xored = [arr[0],                arr[0]^arr[1],...,arr[0]^arr[1]^...^arr[i]^...^arr[n] ] of comulative xored elements of arr
            xored[0] = arr[0]
            for i in range(1,len(arr)):
                xored[i] = xored[i-1]^arr[i]

            # now, because of the XOR property of x^x=0 and its distributive natur we get xored[L-1]^xored[R] = arr[0]^...^.arr[L-1]^arr[0]^...^arr[R]=arr[L]^...^arr[R] as required 
            # (unless L==0 then the answer is simply xored[R])
            for i in range(len(queries)):
                L = queries[i][0]
                R = queries[i][1]
                if L > 0:
                    ans[i] = xored[L-1]^xored[R]
                else: 
                    ans[i] = xored[R]
            return ans        


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        arr.insert(0, 0)
        for i in range(1, len(arr)):
            arr[i] ^= arr[i-1]
        return [arr[a] ^ arr[b+1] for a, b in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(1, len(arr)):
            arr[i] ^= arr[i - 1]
        ret = []
        for l, r in queries:
            ret.append(arr[r] if l == 0 else arr[r] ^ arr[l - 1])
        return ret

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        ans=[]
        ht=[arr[0]]
        for i in range(1,len(arr)):
            ht.append(ht[-1]^arr[i])
        
        for i,j in queries:
            ans.append(ht[j]^(ht[i-1] if i>0 else 0))
        return ans

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        acc = [0]
        for i in range(len(arr)):
            acc.append(acc[i]^arr[i])
        result = []
        for q in queries:
            result.append(acc[q[0]]^acc[q[1]+1])
        return result

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        pre_xor = [0]
        size_arr=len(arr)
        if size_arr%2==0:
            for i in range (0,size_arr,2):
                pre_xor.append(pre_xor[i]^arr[i])
                pre_xor.append(pre_xor[i+1]^arr[i+1])
        else:
            pre_xor.append(pre_xor[0]^arr[0])
            for i in range (1,size_arr,2):
                pre_xor.append(pre_xor[i]^arr[i])
                pre_xor.append(pre_xor[i+1]^arr[i+1])
                
                
            
            

        out_xor = []
        for L, R in queries:
            out_xor.append(pre_xor[L]^pre_xor[R+1])
        return out_xor


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(1, len(arr)):
            arr[i] ^= arr[i-1]
        
        res = []
        for q in queries:
            res.append(arr[q[1]] ^ (0 if q[0] <= 0 else arr[q[0]-1]))
        return res

class Solution:
    def xorQueries(self, A: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(len(A) - 1):
            A[i + 1] ^= A[i]
    # prefix  xor
        return [A[j] ^ A[i - 1] if i else A[j] for i, j in queries] 
    # if i == 0  then a[j]


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(len(arr) - 1):
            arr[i + 1] ^= arr[i]
        return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        a=arr
        q=queries
        l=[]
        for i in range(len(a)-1):
            a[i+1]^=a[i]
        print(a)
        for i,j in q:
            if i:
                l.append(a[j]^a[i-1])
            else:
                l.append(a[j])
        return (l)

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        # result=[]
        # for i in range(len(queries)):
        #     start=queries[i][0]
        #     end=queries[i][1];val=arr[start]
        #     while start != end+1:
        #         if start!=end:
        #             val=val^arr[start+1]
        #             start+=1
        #         else:
        #             result.append(val)
        #             break
        # return result
                    
        prefix = [None]*len(arr)
        res = [None]*len(queries)
        prefix[0]=arr[0]
        for i in range(1,len(arr)):
            prefix[i]=prefix[i-1]^arr[i]
        for i in range(len(queries)):
            if queries[i][0]==0:
                res[i]=prefix[queries[i][1]]
                continue
            res[i]=prefix[queries[i][1]]^prefix[queries[i][0]-1]
        return res
                


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        \"\"\"
        https://leetcode-cn.com/problems/xor-queries-of-a-subarray/solution/zi-shu-zu-yi-huo-cha-xun-by-leetcode-solution/
        * pre[0] = 0
          pre[i] = arr[0] ^ arr[1] ^ ... ^ arr[i - 1]
          arr[Li] ^ ... ^ arr[Ri] = pre[Li] ^ pre[Ri + 1]
        \"\"\"
        # pre = [0]
        # for num in arr:
        #     pre.append(pre[-1] ^ num)
        # ans = list()
        # for x, y in queries:
        #     ans.append(pre[x] ^ pre[y + 1])
        # return ans
    
        # for i in range(len(arr) - 1):
        #     arr[i + 1] ^= arr[i]
        for i in range(1, len(arr)):
            arr[i] = arr[i]^arr[i-1]
        return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries]


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        res = []
        for i in range(len(arr) - 1):
            arr[i+1] = arr[i+1] ^ arr[i]
        for i in queries:
            if i[0] == 0:
                res.append(arr[i[1]])
            else:
                res.append(arr[i[1]] ^ arr[i[0] - 1])
        return res

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        curr = 0
        cum_sum = []
        res = []
        for n in arr:
            curr ^= n 
            cum_sum.append(curr)
        
        for start, end in queries:
            x = cum_sum[end] ^ (cum_sum[start-1] if start > 0 else 0)
            res.append(x)
        return res


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xrr= [0 for i in range(len(arr))]
        xrr[0] = arr[0]
        for i in range(1,len(arr)):
            xrr[i] = xrr[i-1] ^ arr[i]
        res = []
        for q in queries:
            l = q[0]
            r = q[1]
            if l == r:
                res.append(arr[l])
            elif l == 0:
                res.append(xrr[r])
            else:
                res.append(xrr[r] ^ xrr[l-1])
        return res
            
            
        


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        def constSeg(tree, n, arr):
            tree[n:] = arr
            
            for i in range(n-1,0,-1):
                tree[i] = tree[2*i] ^ tree[2*i+1]
        
        def getQuery(beg, end):
            beg += n
            end += n
            
            ans = 0
            
            while(beg<end):
                if beg&1:
                    ans ^= tree[beg]
                    beg += 1
                if end&1:
                    end -= 1
                    ans ^= tree[end]
                
                beg //= 2
                end //=2
            
            return ans
                    
        n = len(arr)
        tree = [0]*(2*len(arr))
        constSeg(tree,len(arr),arr)
        
        ans = []
        for i in queries:
            ans.append(getQuery(i[0], i[1]+1))
        
        return ans
            
        


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        prefix = []
        cur = 0
        for num in arr:
            cur = cur ^ num
            prefix.append(cur)
        ans = []
        for l, r in queries:
            if l == 0:
                ans.append(prefix[r])
            else:
                ans.append(prefix[l-1] ^ prefix[r])
        
        return ans


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        #the poor way to do this is to just go through and Xor the
        res = []
        for i in range(1,len(arr)):
            arr[i] ^= arr[i-1]
        for i,j in queries:
            if i == 0:
                res.append(arr[j])
            else:
                res.append(arr[i-1] ^ arr[j])
        return res #so this is the absurdly slow way to do it though we should be able to memoize in some way?


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        prefix = []
        prev = 0
        for a in arr:
            prefix.append(prev^a)
            prev = prev^a
        
        #print(prefix)
        ans = []
        for left, right in queries:
            if left == 0:
                ans.append(prefix[right])
            else:
                ans.append(prefix[right] ^ prefix[left-1])
        
        return ans

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(len(arr) - 1):
            arr[i + 1] ^= arr[i]  
        return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries]

class Solution:
    tree = []
    n = 0
    def SegmentTree(self, arr):
        nonlocal tree, n
        n = len(arr)
        tree = [0]*2*n
        for i in range(n):
            tree[i+n] = arr[i]
        for j in range(n-1, 0, -1):
            tree[j] = tree[2 * j] ^ tree[2 * j + 1]
            
    def xor(self, frm, to):
        nonlocal tree, n
        frm += n
        to += n
        value = 0
        while(frm < to):
            if(frm & 1 == 1):
                value ^= tree[frm]
                frm += 1
            if(to & 1 == 1):
                to -= 1
                value ^= tree[to]
            frm >>= 1
            to >>= 1
        return value
               
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        self.SegmentTree(arr)
        result = []        
        for query in queries:
            result.append(self.xor(query[0], query[1]+1))
        return result


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        sa = [0] + arr[:]
        for i in range(1, len(sa)):
            sa[i] ^= sa[i - 1]
        ret = []
        for l, r in queries:
            ret.append(sa[r + 1] ^ sa[l])
        return ret

class Solution:
    tree = []
    n = 0
    def SegmentTree(self, arr):
        nonlocal tree, n
        n = len(arr)
        tree = [0]*2*n
        for i in range(n):
            tree[i+n] = arr[i]
        for j in range(n-1, 0, -1):
            tree[j] = tree[2 * j] ^ tree[2 * j + 1]
        #print(tree)
    def xor(self, frm, to):
        nonlocal tree, n
        frm += n
        to += n
        value = 0
        while(frm < to):
            if(frm & 1 == 1):
                value ^= tree[frm]
                frm += 1
            if(to & 1 == 1):
                to -= 1
                value ^= tree[to]
            frm >>= 1
            to >>= 1
        
        return value
            
        
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        self.SegmentTree(arr)
        result = []        
        for query in queries:
            #print(query[0], query[1]+1) DEBUG PRINT
            result.append(self.xor(query[0], query[1]+1))

        return result


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        xors = []
        x = 0
        for num in arr:
            x ^= num
            xors.append(x)
        
        ans = []
        for i, j in queries:
            
            if i == 0:
                ans.append(xors[j])
            else:
                ans.append(xors[j] ^ xors[i-1])
        
        return ans

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        out=[]
        tree = [0]*(2*n)
        for i in range(n):
            tree[i+n] = arr[i]
        for i  in range(n-1,0,-1):
            tree[i] = tree[i << 1]^tree[i << 1 | 1]
        for q in queries:
            res = 0
            l = q[0]+n
            r = q[1]+n+1
            while l < r:
                if l & 1:
                    res = res^tree[l]
                    l=l+1
                if r & 1:
                    r=r-1
                    res = res^tree[r]
                l>>=1
                r>>=1
            out.append(res)
        return out

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        pre_xor = [0]
        size_arr=len(arr)
        if size_arr%2==0:
            for i in range (0,size_arr,2):
                pre_xor.append(pre_xor[-1]^arr[i])
                pre_xor.append(pre_xor[-1]^arr[i+1])
        else:
            pre_xor.append(pre_xor[-1]^arr[0])
            for i in range (1,size_arr,2):
                pre_xor.append(pre_xor[-1]^arr[i])
                pre_xor.append(pre_xor[-1]^arr[i+1])
                
                
            
            

        out_xor = []
        for L, R in queries:
            out_xor.append(pre_xor[L]^pre_xor[R+1])
        return out_xor


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        prefix = [0]
        for a in arr:
            prefix.append(prefix[-1]^a)
        ans = []
        for l, r in queries:
            ans.append(prefix[r+1]^prefix[l])
        return ans

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        pre_xor = [0]
        if len(arr)%2==0:
            for i in range (0,len(arr),2):
                pre_xor.append(pre_xor[i]^arr[i])
                pre_xor.append(pre_xor[i+1]^arr[i+1])
        else:
            pre_xor.append(pre_xor[0]^arr[0])
            for i in range (1,len(arr),2):
                pre_xor.append(pre_xor[i]^arr[i])
                pre_xor.append(pre_xor[i+1]^arr[i+1])
                
                
            
            

        out_xor = []
        for L, R in queries:
            out_xor.append(pre_xor[L]^pre_xor[R+1])
        return out_xor


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        if arr == []:
            return []
        res=[]
        pre=[arr[0]]
        for i in range(1,len(arr)):
            pre.append(arr[i]^pre[-1])
            
        for i in range(0,len(queries)):
            xor=0
            if queries[i][0] == queries[i][1]:
                res.append(arr[queries[i][0]])
            elif (abs(queries[i][0] - queries[i][1]) == 1):
                res.append(arr[queries[i][0]] ^ arr[queries[i][1]])
            else:
                if queries[i][0] == 0:
                    res.append(pre[queries[i][1]])
                else:
                    res.append(pre[queries[i][1]]^pre[queries[i][0]-1])
        print(res)
        return(res)
                    
                


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        # precompute xor values
        for i in range(1,len(arr)):
            arr[i] ^= arr[i-1]
            
        for i, q in enumerate(queries):
            if q[0] == 0:
                queries[i] = arr[q[1]]    
            else:
                queries[i] = arr[q[0]-1] ^ arr[q[1]]
        return queries

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        acc = list(accumulate([0] + arr, xor))
        return [acc[a] ^ acc[b + 1] for a, b in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        px = arr[:]
        
        for i in range(1, len(px)):
            px[i] ^= px[i-1]
        
        res = []
        
        for q in queries:
            s, e = q[0], q[1]
            r = px[e]

            if s: r ^= px[s-1]
            res.append(r)
        
        return res
            


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        b = [arr[0]]
        for a in arr[1:]:
            b.append(b[-1]^a)
            
        ans = []
        for q in queries:
            r = b[q[1]]
            if q[0]>0:
                r ^= b[q[0]-1]
            ans.append(r)
            
        return ans
            
        


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        store = {}
        n= len(arr)
        curr = 0
        store[-1]=0
        for i in range(n):
            curr^=arr[i]
            
            store[i]=curr
        
        return [ store[b]^store[a-1] for a,b in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        prefixSum = [0]*len(arr)
        prefixSum[0] = arr[0]
        result = []
        for i in range(1,len(arr)):
            prefixSum[i] = prefixSum[i-1] ^ arr[i]
        for i in queries:
            if(i[0] == 0):
                result.append(prefixSum[i[1]])
                continue
            result.append(prefixSum[i[1]] ^ prefixSum[i[0]-1])
        return(result)


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        n = len(arr)
        prefix = [0] * (n+1)
        for i in range(n):
            prefix[i+1] = prefix[i] ^ arr[i] 
        
        res = []
        for x, y in queries:
            res.append( prefix[y+1] ^ prefix[x] )
            
        return res
        


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        lookup=[0]*len(arr)
        lookup[0]=arr[0]
        for i in range(1,len(arr)):
            lookup[i] = lookup[i-1]^arr[i]

        r=[]
        for i in range(len(queries)):
            if queries[i][0]==0:
                r.append(lookup[queries[i][1]])
            else:
                tmp=lookup[queries[i][1]]^lookup[queries[i][0]-1]
                r.append(tmp)
        return r

        \"\"\"\"\"\"
        r=[]
        for i in range(len(queries)):
            
            tmp=arr[queries[i][0]:queries[i][1]+1]
            #print(tmp)
            s= tmp[0]
            if len(tmp) >1:
                for i in range(1,len(tmp)):
                    s=s^tmp[i]
            #print(s)
            #print(\"----\")
            r.append(s)
        return r
        \"\"\"\"\"\"

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        m = len(queries)
        d = {}
        res = []
        d['0 0'] = arr[0]
        for i in range(1, n):
            key = '{} {}'.format(0, i)
            pkey = '{} {}'.format(0, i-1)
            d[key] = d[pkey] ^ arr[i]
        print(d)
        for i in range(0, m):
            (u,v) = queries[i]
            s = 0
            # for j in range(u, v + 1):
                # key = '{u} {v}'.format(u=u, v=j)
                # if key in d:
                #     s = d[key]
                #     continue
                # s = s ^ arr[j]
                # d[key] = s
            key2 = '{u} {v}'.format(u=u, v=v)
            if key2 in d:
                res.append(d[key2])
                continue

            pkey = '{} {}'.format(0, u - 1)
            key = '{} {}'.format(0, v)
            s = d[pkey] ^ d[key]
            print(d[pkey], d[key], s)
            res.append(s)
        return res

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(len(arr) - 1):
            arr[i + 1] ^= arr[i]
        
        return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        res=[]
        n=len(arr)
        tmp=[arr[0]]
        for i in range(1,n):
            tmp.append(tmp[-1]^arr[i])
        for x,y in queries:
            if x==0:
                res.append(tmp[y])
            else:
                res.append(tmp[x-1]^tmp[y])
        return res

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        for i in range(1, len(arr)):
            arr[i] = arr[i-1] ^ arr[i]
        return [arr[j] if i == 0 else arr[i-1]^arr[j] for i, j in queries]

from itertools import accumulate

import operator

class Solution:
  def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
    x = list(accumulate(arr, operator.__xor__, initial = 0))
    return [x[i] ^ x[j + 1] for i, j in queries]

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        ans = []
        a = [arr[0],]
        for i in range(1,len(arr)):
            a.append(arr[i]^a[i-1])
        for q in queries:
            if(q[0]==0):
                ans.append(a[q[1]])
            else:
                ans.append(a[q[1]]^a[q[0]-1])
        return ans


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xor_arr = [0]*len(arr)
        xor_arr[0] = arr[0]
        for i in range(1,len(arr)):
            xor_arr[i] = xor_arr[i-1] ^ arr[i]

        res = [0]*len(queries)
        for i, (s,e) in enumerate(queries):
            if s == e:
                res[i] = arr[s]
            elif s == 0:
                res[i] = xor_arr[e]
            else:
                res[i] = xor_arr[e] ^ xor_arr[s-1]
                
        return res

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xors=[0]
        for a in arr:
            xors.append(xors[-1]^a)
        res=[]
        for i,j in queries:
            res.append(xors[j+1]^xors[i])
        return res