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.
from sys import stdin,stdout
input = stdin.readline

from collections import deque

def main():
    #t = int(input())
    t = 1
    for z in range(t):
        n = int(input())
        #a,b,c = map(int,input().split())
        ai = list(map(int,input().split()))
        def trans(num):
            ans = [0]*21
            j = -1
            for i in list(map(int,list(bin(num)[2:])))[::-1]:
                ans[j] = i
                j-=1
            return ans
        def sum2(num1,num2):
            #print(num1,num2)
            num3 = [0]*21
            for i in range(21):
                num3[i] = num1[i] + num2[i]
            return num3
        def xor2(num1,num2, amount):
            if type(num2) is int:
                num2 = trans(num2)
            num3 = [0]*21
            for i in range(21):
                if num2[i] == 1:
                    num3[i] = amount - num1[i]
                else:
                    num3[i] = num1[i]
            return num3
        def create(ai):
            tr = [[[trans(ai[i]),i,i,0] for i in range(n)]]
            n2 = n
            while n2 > 1:
                n3 = n2 // 2 + n2 % 2
                tr += [[[trans(0),n,0,0] for j in range(n3)]]
                for i in range(n2):
                    tr[-1][i//2][0] = sum2(tr[-1][i//2][0],tr[-2][i][0])
                    tr[-1][i//2][1] = min(tr[-1][i//2][1],tr[-2][i][1])
                    tr[-1][i//2][2] = max(tr[-1][i//2][2],tr[-2][i][2])
                n2 = n3
            return tr
        def change(l, r, v):
            d = deque()
            d.append([-1,0])
            pq = [[] for i in range(len(tr))]
            while len(d) > 0:
                i,j = d.pop()
                if tr[i][j][1] >= l and tr[i][j][2] <= r:
                    tr[i][j][0] = xor2(tr[i][j][0],v,(tr[i][j][2]-tr[i][j][1]+1))
                    tr[i][j][3] ^= v
                    if i != -1:
                        pq[i+1] += [j//2]
                elif max(tr[i][j][1],l) <= min(tr[i][j][2],r):
                    d.append([i-1,j*2])
                    if len(tr[i-1]) > j * 2 + 1:
                        d.append([i-1,j*2+1])
            for i in range(-len(tr)+1,-1):
                temp = len(tr[i-1])
                for j in pq[i]:
                    if len(tr[i-1]) > j * 2 + 1:
                        tr[i][j][0] = xor2(sum2(tr[i-1][j*2][0],tr[i-1][j*2+1][0]),tr[i][j][3],(tr[i][j][2]-tr[i][j][1]+1))
                    else:
                        tr[i][j][0] = xor2(tr[i-1][j*2][0],tr[i][j][3],(tr[i][j][2]-tr[i][j][1]+1))
                    pq[i+1] += [j//2]
            if len(tr) != 1:
                tr[-1][0][0] = xor2(sum2(tr[-2][0][0],tr[-2][1][0]),tr[-1][0][3],(tr[-1][0][2]-tr[-1][0][1]+1))
        
        def count(l,r):
            d = deque()
            d.append([-1,0,0])
            ans = trans(0)
            while len(d) > 0:
                i,j,num = d.pop()
                if tr[i][j][1] >= l and tr[i][j][2] <= r:
                    ans = sum2(ans,xor2(tr[i][j][0] , num,(tr[i][j][2]-tr[i][j][1]+1)))
                elif max(tr[i][j][1],l) <= min(tr[i][j][2],r):
                    d.append([i-1,j*2,num ^ tr[i][j][3]])
                    if len(tr[i-1]) > j * 2 + 1:
                        d.append([i-1,j*2+1,num + tr[i][j][3]])
            return ans
        tr = create(ai)
        m = int(input())

        def anss(num):
            ans = 0
            for i in range(-1,-22,-1):
                ans += num[i]*2**(abs(i)-1)
            return ans
        for i in range(m):
            ti = list(map(int,input().split()))
            if ti[0] == 1:
                print(anss(count(ti[1]-1,ti[2]-1)))
            else:
                change(ti[1]-1,ti[2]-1,ti[3])
           
main()
