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;

int a[100004],n,m,cs[400004];
const int MAX=20;

struct tree{
	long long sum=0;
	int cnt1[MAX];
}dp[400004];

tree merge(int o)
{
	tree re;
	re.sum=o;
	for(int i=0; i<MAX; i++)
	{
		int cur=(1<<i);
		if((cur&o)>0) re.cnt1[i]=1;
		else re.cnt1[i]=0;
	}
	return re;
}

tree merge2(tree b1,tree b2)
{
	tree re;
	re.sum=b1.sum+b2.sum;
	for(int i=0; i<MAX; i++) re.cnt1[i]=b1.cnt1[i]+b2.cnt1[i];
	return re;
}

void build(int l,int r,int i)
{
	if(l==r) dp[i]=merge(a[l]);
	else
	{
		int mid=(l+r)/2;
		build(l,mid,i*2);
		build(mid+1,r,i*2+1);
		dp[i]=merge2(dp[i*2],dp[i*2+1]);
	}
}

void xorf(int i,int l,int r)
{
	//printf("l=%d r=%d i=%d cs=%d sum=%d\n",l,r,i,cs[i],dp[i].sum);
	if(cs[i]==0) return;
	if(l==r)
	{
		int val=cs[i];
		cs[i]=0;
		int ne=dp[i].sum^val;
		dp[i]=merge(ne);
	}
	else
	{
		int val=cs[i];
		cs[i]=0;
		cs[i*2]^=val;
		cs[i*2+1]^=val;
		int mid=(l+r)/2;
		xorf(i*2,l,mid);
		xorf(i*2+1,mid+1,r);
		int ne=dp[i].sum;
		for(int j=0; j<MAX; j++)
		{
			int cur=1<<j;
			if((cur&val)>0)
			{
				int neg=dp[i].cnt1[j];
				int teg=(r-l+1)-neg;
				int diff=teg-neg;
				dp[i].cnt1[j]=teg;
				ne+=(diff*cur);
			}
		}
		dp[i].sum=ne;
	}
}

long long query(int l,int r,int x,int y,int i)
{
	//printf("%d %d %d %d\n",l,r,i,cs[i]);
	if(l>y || r<x) return 0LL;
	//xorf(i,l,r);
	//printf("%d %d %d\n",l,r,dp[i].sum);
	if(l==r) return dp[i].sum;
	else if(l>=x && r<=y) return dp[i].sum;
	else
	{
		int mid=(l+r)/2;
		return query(l,mid,x,y,i*2)+query(mid+1,r,x,y,i*2+1);
	}
}

void update(int l,int r,int x,int y,int val,int i)
{
	if(l>y || r<x) return;
	//xorf(i,l,r);
	if(l==r)
	{
		cs[i]^=val;
		xorf(i,l,r);
		//a[l]=dp[i].sum;
		//printf("%d %d %d\n",l,r,dp[i].sum);
	}
	else if(l>=x && r<=y)
	{
		cs[i]^=val;
		xorf(i,l,r);
		//printf("%d %d %d\n",l,r,dp[i].sum);
	}
	else
	{
		int mid=(l+r)/2;
		update(l,mid,x,y,val,i*2);
		update(mid+1,r,x,y,val,i*2+1);
		dp[i]=merge2(dp[i*2],dp[i*2+1]);
	}
}


int main()
{
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d",&a[i]);
	build(0,n-1,1);
	int t,l,r,x;
	scanf("%d",&m);
	for(int i=0; i<m; i++)
	{
		scanf("%d %d %d",&t,&l,&r);
		l--;
		r--;
		if(t==1)
		{
			long long ans=query(0,n-1,l,r,1);
			printf("%I64d\n",ans);
		}
		else
		{
			scanf("%d",&x);
			update(0,n-1,l,r,x,1);
			//for(int j=0; j<n; j++) printf("%d ",a[j]);
			//printf("\n");
		}
	}
	return 0;
}
