You've got an array *a*, consisting of *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. You are allowed to perform two operations on this array:
 1.  Calculate the sum of current array elements on the segment [*l*, *r*], that is, count value *a*<sub class="lower-index">*l*</sub> + *a*<sub class="lower-index">*l* + 1</sub> + ... + *a*<sub class="lower-index">*r*</sub>. 1.  Apply the xor operation with a given number *x* to each array element on the segment [*l*, *r*], that is, execute <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2ef04d094daf2dcff9a998a558bd9cab93bbd012.png" style="max-width: 100.0%;max-height: 100.0%;"/>. This operation changes exactly *r* - *l* + 1 array elements. 
Expression <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b364f2e04c665b78b924ec10666327a4ef4635bc.png" style="max-width: 100.0%;max-height: 100.0%;"/> means applying bitwise xor operation to numbers *x* and *y*. The given operation exists in all modern programming languages, for example in language C++ and Java it is marked as "^", in Pascal — as "xor".

You've got a list of *m* operations of the indicated type. Your task is to perform all given operations, for each sum query you should print the result you get.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the size of the array. The second line contains space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the original array.

The third line contains integer *m* (1 ≤ *m* ≤ 5·10<sup class="upper-index">4</sup>) — the number of operations with the array. The *i*-th of the following *m* lines first contains an integer *t*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2) — the type of the *i*-th query. If *t*<sub class="lower-index">*i*</sub> = 1, then this is the query of the sum, if *t*<sub class="lower-index">*i*</sub> = 2, then this is the query to change array elements. If the *i*-th operation is of type 1, then next follow two integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*). If the *i*-th operation is of type 2, then next follow three integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *x*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*, 1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>). The numbers on the lines are separated by single spaces.
def getSum(st,lazy,qe,qs,start,end,index):
    if(lazy[index]!=0):
        st[index]^=k
        if(start!=end):
            lazy[2*index+1]=1
            lazy[2*index+2=1
        lazy[index]=0

    if(qs>se or qe<ss):
        return 0
    
    if(qs<=ss and se<=qe):
        return st[index]
    
    int mid = (start+end)//2
    return getSum(st,lazy,qe,qs,start,mid,2*index+1)+getSum(st,lazy,qe,qs,mid+1,end,2*index+2)

def constructSTUtil(a,st,start,end,index):
    if(start==end):
        st[index]=a[start]
        return st[index]
        
    mid = (start+end)//2
    
    return constructSTUtil(a,st,start,mid,2*index+1)+constructSTUtil(a,st,mid+1,end,2*index+2)
    
def update(st,lazy,qe,qs,start,end,index,k):
    if(lazy[index]!=0):
        st[index]^=k
        if(start!=end):
            lazy[2*index+1]=1
            lazy[2*index+1]=1
        lazy[index]=0
        
    if(qe<ss or qs>se):
        return
    if(qs<=ss and qe>=se):
        st[index]^=k
        if(start!=end):
            lazy[2*index+1]=1
            lazy[2*index+1]=1
        return
    
    mid =(start+end)//2
    update(st,lazy,qe,qs,start,mid,2*index+1,k)
    update(st,lazy,qe,qs,mid+1,end,2*index+2,k)
    
def constructST(a,n):
    st = [0]*4*n
    constructSTUtil(a,st,0,n-1,0)
    return st
if __name__ == "__main__:
    n = int(input())
    a = [int(x) for x in input().split()]
    lazy = [0]*4*n
    q = int(input())
    st = constructST(a,n)
    for i in range(q):
        t = [int(x) for x in input().split())
            l=t[1]
            r =t[2]
            if(len(t)==3):
                print(getSum(st,lazy,l,r,0,n-1,0))
            else:
                k = t[3]
                update(st,lazy,l,r,0,n-1,0,k)
            
        
            
        
        