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.
n=int(input())

arr=list(map(int,input().split()))

tree=[[0,[0 for i in range(20)]] for j in range(4*n)]
lazy=[0 for i in range(4*n)]


def build(node,start,end):

    if start==end:
        tree[node][0]=arr[start]
        for i in range(20):
            if arr[start]&(1<<i)!=0:
                tree[node][1][i]+=1
        return
    mid=start+(end-start)//2
    build(node*2,start,mid)
    build(node*2+1,mid+1,end)

    tree[node][0]=tree[node*2][0]+tree[node*2+1][0]
    for i in range(20):
            tree[node][1][i]=tree[node*2][1][i]+tree[node*2+1][1][i]
build(1,0,n-1)

def propogate(node,start,end):
    

    if start==end:
        tree[node][0]^=lazy[node]
        for i in range(20):
            tree[node][1][i]=0
            if (1<<i)&tree[node][0]!=0:
                tree[node][1][i]+=1
        lazy[node]=0
    else:
        lazy[node*2]^=lazy[node]
        lazy[node*2+1]^=lazy[node]
        x=lazy[node]
        lazy[node]=0
        cnt=end-start+1
        for i in range(20):
            if (1<<i)&x!=0:
                number_of_ones=tree[node][1][i]
                number_of_zeros=cnt-tree[node][1][i]
                tree[node][0]+=(number_of_zeros-number_of_ones)*pow(2,i)
                tree[node][1][i]=cnt-tree[node][1][i]

def update(node,start,end,l,r,x):

    propogate(node,start,end)
    if l>end or start>r:
        return
    if l<=start and end<=r:
        lazy[node]^=x
        propogate(node,start,end)
        return
    mid=start+(end-start)//2
    update(node*2,start,mid,l,r,x)
    update(node*2+1,mid+1,end,l,r,x)
    tree[node][0]=tree[node*2][0]+tree[node*2+1][0]
    for i in range(20):
        tree[node][1][i]=tree[node*2][1][i]+tree[node*2+1][1][i]

def query(node,start,end,l,r):

    propogate(node,start,end)
    if start>r or l>end:
        return 0
    if l<=start and end<=r:
        return tree[node][0]
    mid=start+(end-start)//2
    left=query(node*2,start,mid,l,r)
    right=query(node*2+1,mid+1,end,l,r)
    return left+right

m=int(input())

for _ in range(m):
    lst=list(map(int,input().split()))
    if lst[0]==1:
        print(query(1,0,n-1,lst[1]-1,lst[2]-1))
    else:
        update(1,0,n-1,lst[1]-1,lst[2]-1,lst[3])
   