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 collections import defaultdict


def build_tree(arr, tree, id, l, r):
    if l == r:
        tree[id] = arr[l]
        return
    m = (l + r) // 2
    left_id = 2 * id + 1
    right_id = 2 * id + 2
    build_tree(arr, tree, left_id, l, m)
    build_tree(arr, tree, right_id, m + 1, r)
    tree[id] = (
        tree[left_id][0] + tree[right_id][0],
        tree[left_id][1] + tree[right_id][1],
    )


def down(tree, lazy, id, l, r):
    if l != r:
        lazy[2 * id + 1] += lazy[id]
        lazy[2 * id + 2] += lazy[id]
    if lazy[id] % 2 != 0:
        tree[id] = (tree[id][1], tree[id][0])
    lazy[id] = 0


def query(tree, lazy, id, l, r, fr, to):
    if lazy[id] != 0:
        down(tree, lazy, id, l, r)

    if fr > r or to < l:
        return (0, 0)

    if fr <= l and r <= to:
        return tree[id]

    m = (l + r) // 2
    left = query(tree, lazy, 2 * id + 1, l, m, fr, to)
    right = query(tree, lazy, 2 * id + 2, m + 1, r, fr, to)
    return (left[0] + right[0], left[1] + right[1])


def update(tree, lazy, id, l, r, fr, to):
    if lazy[id] != 0:
        down(tree, lazy, id, l, r)
    if fr > r or to < l:
        return
    if fr <= l and r <= to:
        tree[id] = (tree[id][1], tree[id][0])
        if l != r:
            lazy[2 * id + 1] += 1
            lazy[2 * id + 2] += 1
        return
    m = (l + r) // 2
    left_id = 2 * id + 1
    right_id = 2 * id + 2
    update(tree, lazy, left_id, l, m, fr, to)
    update(tree, lazy, right_id, m + 1, r, fr, to)
    tree[id] = (
        tree[left_id][0] + tree[right_id][0],
        tree[left_id][1] + tree[right_id][1],
    )


MAX_BITS = 21


def bits(n):
    res = []
    for i in range(MAX_BITS):
        if n & (1 << i) > 0:
            res.append(i)
    return res


def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    queries = []
    for _ in range(int(input())):
        queries.append(list(map(int, input().split())))

    bits_arr = [[(0, 1)] * n for _ in range(MAX_BITS)]
    for i, num in enumerate(arr):
        for b in bits(num):
            bits_arr[b][i] = (1, 0)

    tree = [defaultdict(lambda: (0, 0)) for _ in range(MAX_BITS)]
    lazy = [defaultdict(int) for _ in range(MAX_BITS)]
    for a, t in zip(bits_arr, tree):
        build_tree(a, t, 0, 0, n - 1)

    for q in queries:
        if q[0] == 1:
            ans = 0
            [l, r] = q[1:]
            for i in range(MAX_BITS):
                bits_1, _ = query(tree[i], lazy[i], 0, 0, n - 1, l - 1, r - 1)
                ans += bits_1 * (1 << i)
            print(ans)
        else:
            [l, r, x] = q[1:]
            for b in bits(x):
                update(tree[b], lazy[b], 0, 0, n - 1, l - 1, r - 1)


solve()
