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.
#include <bits/stdc++.h>
using namespace std;
#define db double
#define il inline
#define fir first
#define sec second
#define eps (1e-10)
#define pb push_back
#define ll long long
#define mkp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define lowbit(a) (a & (-a))
#define SZ(a) ((int)a.size())
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define SPLIT cout << "=========\n";
#define GG { cout << "NO\n"; return; }
#define pll pair<long long, long long>
#define equals(a, b) (fabs((a) - (b)) < eps)
const int N=1e6+10;
constexpr int ON = 0;
constexpr int CW = -1;
constexpr int CCW = 1;
constexpr int BACK = 2;
constexpr int FRONT = -2;
const db pi = acos(-1.000);
constexpr int maxn = 5e5 + 100;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF =  0x3f3f3f3f3f3f3f3f;
constexpr int mod = 1e9 + 7; /* 998244353 */
constexpr int dir[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};

int n, m, x;
int a[maxn];

ll sum[21][maxn]; bool lazy[21][maxn];

void push_down(int id, int p, int l, int r) {
    if (lazy[id][p]) {
        int mid = l + r >> 1;
        sum[id][p << 1] = mid - l + 1 - sum[id][p << 1];
        sum[id][p << 1 | 1] = r - mid - sum[id][p << 1 | 1];
        lazy[id][p << 1] ^= 1;
        lazy[id][p << 1 | 1] ^= 1;
        lazy[id][p] = 0;
    }
}

void build(int id, int p, int l, int r) {
    if (l == r) {
        sum[id][p] = (a[l] >> id) & 1;
        return ;
    }
    int mid = l + r >> 1;
    build(id, p << 1, l, mid);
    build(id, p << 1 | 1, mid + 1, r);
    sum[id][p] = sum[id][p << 1] + sum[id][p << 1 | 1];
}

void update(int id, int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        sum[id][p] = r - l + 1 - sum[id][p];
        lazy[id][p] ^= 1;
        return ;
    }
    push_down(id, p, l, r);
    int mid = l + r >> 1;
    if (ql <= mid) update(id, p << 1, l, mid, ql, qr);
    if (mid < qr) update(id, p << 1 | 1, mid + 1, r, ql, qr);
    sum[id][p] = sum[id][p << 1] + sum[id][p << 1 | 1];
}

ll query(int id, int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[id][p];
    push_down(id, p, l, r);
    int mid = l + r >> 1;
    ll ans = 0;
    if (ql <= mid) ans += query(id, p << 1, l, mid, ql, qr);
    if (mid < qr) ans += query(id, p << 1 | 1, mid + 1, r, ql, qr);
    return ans;
}

void solve(int cas) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i <= 20; ++i) {
        build(i, 1, 1, n);
    }
    cin >> m;
    while (m--) {
        int op, l, r, x; cin >> op >> l >> r;
        if (op == 1) {
            ll ans = 0;
            for (int i = 0; i <= 20; ++i) {
                ans += query(i, 1, 1, n, l, r) * (1 << i);
            }
            cout << ans << '\n';
        } else {
            cin >> x;
            for (int i = 0; i <= 20; ++i) {
                if ((x >> i) & 1)
                    update(i, 1, 1, n, l, r);
            }
        }
    }
}



signed main() {
    // cout << fixed << setprecision(10);
    // srand(time(0));
    ios::sync_with_stdio(false); cin.tie(nullptr);
    // int T; cin>>T; while (T--) solve(1);
    // for (int i = 1; i <= T; ++i) solve(i);
    // brute_force();
    solve(1);
    return 0;
}
