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.
class SegTree:
    def __init__(self,l,r):
        self.l,self.r,self.mask,self.count=l,r,0,[0]*25
        self.left,self.right=None,None
def build(st,a):
    l,r=st.l,st.r
    if l==r:
        for i in range(25):
            st.count[i]=a[l]>>i&1
    else:
        mid=(l+r)>>1
        st.left,st.right=SegTree(l,mid),SegTree(mid+1,r)
        build(st.left,a)
        build(st.right,a)
        for i in range(25):
            st.count[i]=st.left.count[i]+st.right.count[i]
def clear(st):
    l,r=st.l,st.r
    mid=(l+r)>>1
    st.left.mask^=st.mask
    st.right.mask^=st.mask
    for i in range(25):
        if st.mask>>i&1:
            st.left.count[i]=mid-l+1-st.left.count[i]
            st.right.count[i]=r-mid-st.right.count[i]
    st.mask=0
def find(st,a,b):
    l,r=st.l,st.r
    if l==a and r==b:
        return sum(st.count[i]*(1<<i) for i in range(25))
    mid=(l+r)>>1
    clear(st)
    if b<=mid:
        return find(st.left,a,b)
    elif a>mid:
        return find(st.right,a,b)
    return find(st.left,a,mid)+find(st.right,mid+1,b)
def modify(st,a,b,x):
    l,r=st.l,st.r
    if l==a and r==b:
        st.mask^=x
        for i in range(25):
            if x>>i&1:
                st.count[i]=r-l+1-st.count[i]
    else:
        mid=(l+r)>>1
        clear(st)
        if b<=mid:
            modify(st.left,a,b,x)
        elif a>mid:
            modify(st.right,a,b,x)
        else:
            modify(st.left,a,mid,x)
            modify(st.right,mid+1,b,x)
        for i in range(25):
            st.count[i]=st.left.count[i]+st.right.count[i]
n,a,q=int(input()),[0]+list(map(int,input().split())),int(input())
st=SegTree(1,n)
build(st,a)
for i in range(q):
    op=list(map(int,input().split()))
    if op[0]==1:
        print(find(st,op[1],op[2]))
    else:
        modify(st,op[1],op[2],op[3])