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.
import sys
n = int(sys.stdin.readline())
class SegTree:
    def build(self, A, x, lx, rx):
        op = self.op
        st = self.st
        cnt = self.cnt
        if rx - lx == 1:
            if lx < len(A):
                self.cnt[x] = 1
                for i in range(23):
                    if (A[lx] & (1 << i)):
                        self.st[x][i] = 1
                    else:
                        self.st[x][i] = 0
            return
        mid = (lx + rx) >> 1
        a = (x << 1) | 1
        b = (x << 1) + 2
        self.build(A, a, lx, mid)
        self.build(A, b, mid, rx)
        for i in range(23):
            self.st[x][i] = self.st[a][i] + self.st[b][i]
        self.cnt[x] = self.cnt[a] + self.cnt[b]
    def __init__(self, sz, A):
        self.n = 1
        while self.n < sz:
            self.n <<= 1
        self.st = [[0 for x in range(23)] for y in range(self.n << 1)]
        self.cnt = [0] * (self.n << 1)
        self.op = [[0 for x in range(23)] for y in range(self.n << 1)]
        self.build(A, 0, 0, self.n)
    def propagate(self, x, lx, rx):
        op = self.op
        st = self.st
        cnt = self.cnt
        if (rx - lx == 1):
            return
        a = (x << 1) | 1
        b = (x << 1) + 2
        for i in range(23):
            if op[x][i]:
                op[a][i] ^= 1
                op[b][i] ^= 1
                st[a][i] = cnt[a] - st[a][i]
                st[b][i] = cnt[b] - st[b][i]
            op[x][i] = 0
    def _modify(self, l, r, xor_val, x, lx, rx):
        op = self.op
        st = self.st
        cnt = self.cnt
        self.propagate(x, lx, rx)
        if (lx >= r or rx <= l):
            return
        if (lx >= l and rx <= r):
            for i in range(23):
                if (xor_val & (1 << i)):
                    op[x][i] = 1
                    st[x][i] = cnt[x] - st[x][i]
            return
        mid = (lx + rx) >> 1
        a = (x << 1) | 1
        b = (x << 1) + 2
        self._modify(l, r, xor_val, a, lx, mid)
        self._modify(l, r, xor_val, b, mid, rx)
        for i in range(23):
            st[x][i] = st[a][i] + st[b][i]
    def modify(self, l, r, xor_val):
        self._modify(l, r, xor_val, 0, 0, self.n)
    def _query(self, l, r, x, lx, rx):
        op = self.op
        st = self.st
        cnt = self.cnt
        self.propagate(x, lx, rx)
        if (lx >= r or rx <= l):
            return 0
        if (lx >= l and rx <= r):
            sum = 0
            for i in range(23):
                # print(1 << i)
                sum += (1 << i) * st[x][i]
            # print("Sum at ", lx, rx, sum)
            return sum
        mid = (lx + rx) >> 1
        a = (x << 1) | 1
        b = (x << 1) + 2
        return self._query(l, r, a, lx, mid) + self._query(l, r, b, mid, rx)
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)
    def _debug(self, x, lx, rx):
        print("x = ", x, "lx = ", lx, "rx = ", rx)
        print("cnt[x] = ", self.cnt[x])
        for i in range(23):
            print(self.st[x][i], end = " ")
        print("\n")
        if (rx - lx == 1):
            return
        mid = (lx + rx) >> 1
        a = (x << 1) | 1
        b = (x << 1) + 2
        self._debug(a, lx, mid)
        self._debug(b, mid, rx)
    def debug(self):
        self._debug(0, 0, self.n)
A = [int(x) for x in sys.stdin.readline().split()]
m = int(sys.stdin.readline())
st = SegTree(n, A)
# st.debug()
# print(st.st)
while m:
    m -= 1
    q = [int(x) for x in sys.stdin.readline().split()]
    if (q[0] == 1):
        l = q[1] - 1
        r = q[2]
        print(st.query(l, r))
    else:
        l = q[1] - 1
        r = q[2]
        x = q[3]
        st.modify(l, r, x)
