Rt，写的平衡树。

#include <bits/stdc++.h>
#define ls t[u].lson
#define rs t[u].rson
#define ll long long

using namespace std;
const int N=5e5+5,mod=1.1e9+7,MB=1<<20;
void chkmax(int &x,int y){x=max(x,y);}
void chkmin(int &x,int y){x=min(x,y);}
void Add(int &x,int y){x+=y,x%=mod;}
int ab(int x){if(x<0)x=-x;return x;}

int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
	return x*f;
}

struct node{
	int lson,rson,id,val,siz,rd,mx,mi,mip,mxp,tag;
	ll sum;
}t[N];
int n,m,a[N],root[32],rx,ry,rz,ra,rb,rc,rd,re,rf,tot;
struct FastIO
{
	char ib[MB+100],*p,*q;
	char ob[MB+100],*r,stk[128];
	int tp;
	
	FastIO(){p=q=ib,r=ob,tp=0;}
	~FastIO(){fwrite(ob,1,r-ob,stdout);} //析构函数，自动flush 
	
	char read_char() //读入一个字符，注意会读入空白字符，例如空格换行
	{
		if(p==q)
		{
			p=ib,q=ib+fread(ib,1,MB,stdin);
			if(p==q)return 0;
		}
		return *p++;
	}
	template<typename T>
	void read_int(T& x) //读入一个整型变量，int,long long之类的都能读入 
	{
		char c=read_char(),l=0;
		for(x=0;!std::isdigit(c);c=read_char())l=c;
		for(;std::isdigit(c);c=read_char())x=x*10-'0'+c;
		if(l=='-')x=-x;
	}
	
	void write_char(char c) //输出一个字符 
	{
		if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);
		*r++=c;
	}
	template<typename T>
	void write_int(T x) //输出一个整型变量，int,long long之类的都能输出 
	{
		if(x<0)write_char('-'),x=-x;
		do stk[++tp]=x%10+'0';
		while(x/=10);
		while(tp)write_char(stk[tp--]);
	}
}IO;
int getb(int x){
	for(int i=29;i>=0;i--){
		if(x&(1<<i))return i;
	}
	return 0;
}
void update(int u){
	t[u].siz=t[ls].siz+t[rs].siz+1,t[u].sum=t[ls].sum+t[rs].sum+t[u].val;
	t[u].mx=t[u].mi=t[u].val,t[u].mxp=t[u].mip=t[u].id;
	if(t[ls].mx>t[u].mx)t[u].mx=t[ls].mx,t[u].mxp=t[ls].mxp;
	if(t[rs].mx>t[u].mx)t[u].mx=t[rs].mx,t[u].mxp=t[rs].mxp;
	if(t[ls].mi<t[u].mi)t[u].mi=t[ls].mi,t[u].mip=t[ls].mip;
	if(t[rs].mi<t[u].mi)t[u].mi=t[rs].mi,t[u].mip=t[rs].mip;
}

void update_tag(int u,int tag){
  if(!u)return;
	t[u].sum+=1ll*t[u].siz*tag,t[u].mx+=tag,t[u].mi+=tag,t[u].val+=tag,t[u].tag+=tag;
}

void push_down(int u){
	if(t[u].tag)update_tag(ls,t[u].tag),update_tag(rs,t[u].tag),t[u].tag=0;
}

void spilt(int u,int k,int &x,int &y){
  if(!u){x=0;y=0;return;}
  push_down(u);
	if(k>=t[u].id)x=u,spilt(rs,k,rs,y),update(u);
	else y=u,spilt(ls,k,x,ls),update(u);
}

int merge(int x,int y){
  if((!x)||(!y))return x+y;
  push_down(x),push_down(y);
  if(t[x].rd<t[y].rd){t[x].rson=merge(t[x].rson,y),update(x);return x;}
  else {t[y].lson=merge(x,t[y].lson),update(y);return y;}
}

void re_insert(int &u,int x){
  spilt(u,t[x].id-1,rd,re);
  u=merge(merge(rd,x),re);
}

void Delete_mi(int &u,int x){
	int p=t[u].mip;
	spilt(u,p-1,ra,rb),spilt(rb,p,rb,rc);	
	t[rb].val-=x,t[rb].sum-=x,t[rb].mx-=x,t[rb].mi-=x;
	if(t[rb].val!=0)re_insert(root[getb(t[rb].val)],rb);
	u=merge(ra,rc);
}

void Delete_mx(int &u,int x){
	int p=t[u].mxp;
	spilt(u,p-1,ra,rb),spilt(rb,p,rb,rc);
	t[rb].val-=x,t[rb].sum-=x,t[rb].mx-=x,t[rb].mi-=x;
	if(t[rb].val!=0)re_insert(root[getb(t[rb].val)],rb);
	u=merge(ra,rc);
}

int add_node(int x,int id){
	++tot,t[tot].siz=1,t[tot].rd=rand();
	t[tot].val=x,t[tot].sum=t[tot].mi=t[tot].mx=x,t[tot].id=t[tot].mxp=t[tot].mip=id;
  return tot;
}

signed main(void){
//	freopen("date.in","r",stdin);
//	freopen("zhengjie.out","w",stdout);
//	srand(time(0));
	t[0].mx=-mod,t[0].mi=mod;
	IO.read_int(n),IO.read_int(m);
	for(int i=1;i<=n;i++){
		IO.read_int(a[i]);
		int b=getb(a[i]);
    root[b]=merge(root[b],add_node(a[i],i));
	}
	int lasans=0;
	while(m--){
		int op=0,l=0,r=0;
		IO.read_int(op),IO.read_int(l),IO.read_int(r);
		l^=lasans,r^=lasans;
		if(l>r)swap(l,r);
		if(op&1){
			int x=0;
			IO.read_int(x);x^=lasans;
			int b=getb(x);
			spilt(root[b],l-1,rx,ry),spilt(ry,r,ry,rz);
			while(t[ry].mx>x)Delete_mx(ry,x);
			root[b]=merge(merge(rx,ry),rz);
			for(int i=b+1;i<=29;i++){//!!!
//			  printf("%d\n",i);
				spilt(root[i],l-1,rx,ry),spilt(ry,r,ry,rz);
				while(t[ry].mi&&t[ry].mi-x<(1<<i))Delete_mi(ry,x);
				update_tag(ry,-x);
				root[i]=merge(merge(rx,ry),rz);
//				printf("%d\n",i);
			}
		}
		else {
			ll sum=0;
			int mx=-mod,mi=mod;
			for(int i=0;i<=29;i++){
				spilt(root[i],l-1,rx,ry),spilt(ry,r,ry,rz);
		  	sum+=t[ry].sum,chkmax(mx,t[ry].mx),chkmin(mi,t[ry].mi);
		  	root[i]=merge(merge(rx,ry),rz);
			}
			IO.write_int(sum),IO.write_char(' ');
			IO.write_int(mi),IO.write_char(' ');
			IO.write_int(mx),IO.write_char(' ');
			IO.write_char('\n');
			lasans=sum%(1<<20);
		}
	}
	return 0;
}
/*
5 5
1 5 2 3 1 
1 2 4 2
2 2 5
2 1 2
2 3 4
2 1 4
*/