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.
# LUOGU_RID: 110637301
#include<bits/stdc++.h>
#define int long long 
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int SIZE=1e5+50;
int q[SIZE];
int n,cnt;
const int tot=30;
struct Q
{
	int l,r;
	int add;
	int ans[tot];
}t[SIZE<<2];
void build(int l,int r,int p)
{
	t[p].l=l,t[p].r=r;
	if(l==r)
	{
		for(int i=0;i<tot;i++)
		{
			if((q[l]>>i)&1)	t[ls].ans[i]=1;
			else t[p].ans[i]=0;
			return;
		}
	}
	int mid=(l+r)>>1;
	build(l,mid,ls),build(mid+1,r,rs);
	for(int i=0;i<tot;i++)	t[p].ans[i]=t[ls].ans[i]+t[rs].ans[i];
}
void spread(int p)
{
	if(t[p].add)
	{
		int mid=(t[p].l+t[p].r)>>1;
		for(int i=0;i<tot;i++)
		{
			if((t[p].add>>i)&1)
			{
				t[ls].ans[i]=(mid-t[ls].l+1)-t[ls].ans[i];
				t[rs].ans[i]=(t[rs].r-mid)-t[rs].ans[i];
            }
        }
		t[ls].add^=t[p].add:
		t[rs].add^=t[p].add;
        t[p].add=0;
    }
}
void change(int p,int l,int r,int k)
{
	if(t[p].l>=l&&t[p].r<=r)
	{
		for(int i=1;i<=tot;i++)
		{	
        	if((k>>i)&1) t[p].ans[i]=(t[p].r-t[p].l+1)-t[p].ans[i];
        	t[p].add^=k;
        	return;
		}
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)	change(ls,l,r,k);
	if(mid+1<=r)	change(rs,l,r,k);
	for(int i=0;i<tot;i++)	t[p].ans[i]=t[ls].ans[i]+t[rs].ans[i];
}
int ask(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r)
	{
        int ans=0,pow=1;
        for(int i=0;i<tot;i++)
        	ans+=pow*t[p].ans[i],pow<<=1;
        return ans;
    }
	spread(p);
    long long ans=0;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) ans+=ask(ls,l,r);
    if(mid+1<=r) ans+=ask(rs,l,r);
    return ans;
}

signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)	scanf("%lld",&q[i]);
	build(1,1,n);
	scanf("%lld",&cnt);
	for(int i=1;i<=cnt;i++)
	{
		int opt,l,r,k;
		scanf("%lld",&opt);
		scanf("%lld%lld",&l,&r);
		if(opt==1)	printf("%lld\n",ask(1,l,r));
		else	scanf("%lld",&k),change(1,l,r,k);
	}
	return 0;
}