RE on test 10

#include<bits/stdc++.h>
using namespace std;

const int N=200010,M=21000010;
int n,p[N],q;
struct edge{
	int y,nex,c;
}s[N<<1];
vector<pair<int,int> > V[N];
int first[N],len=0,fa[N],sz[N],top[N],val[N],dfn[N],tim,rt[N],T,son[N],tag[M],ls[M],rs[M];
long long sum[N],tot[N],op[M],dep[N];

void ins(int x,int y,int c){
	s[++len]=(edge){y,first[x],c};first[x]=len;
}

void dfs(int x){
	sz[x]=1;
	for(int i=first[x];i!=0;i=s[i].nex) if(s[i].y!=fa[x]){
		fa[s[i].y]=x;val[s[i].y]=s[i].c;dep[s[i].y]=dep[x]+s[i].c;
		dfs(s[i].y);
		if(sz[s[i].y]>sz[son[x]]) son[x]=s[i].y;
	}
}

void dfs_2(int x,int tp){
	dfn[x]=++tim;top[x]=tp;sum[dfn[x]]=val[x];
	if(son[x]) dfs_2(son[x],tp);
	for(int i=first[x];i!=0;i=s[i].nex) if(s[i].y!=son[x] && s[i].y!=fa[x])
		dfs_2(s[i].y,s[i].y);
}

void got(int x){
	int tmp=x;
	while(x){
		V[tmp].push_back(make_pair(dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
}

void ins(int&now,int las,int x,int y,int l=1,int r=n){
	now=++T;
	op[now]=op[las]+sum[y]-sum[x-1];tag[now]=tag[las];
	ls[now]=ls[las],rs[now]=rs[las];
	if(x==l && y==r){tag[now]++;return ;}
	int mid=(l+r)/2;
	if(y<=mid) ins(ls[now],ls[las],x,y,l,mid);
	else if(mid<x) ins(rs[now],rs[las],x,y,mid+1,r);
	else ins(ls[now],ls[las],x,mid,l,mid),ins(rs[now],rs[las],mid+1,y,mid+1,r);
}

long long gas(int now,int x,int y,int l=1,int r=n){
	if(!now) return 0;
	if(x==l && y==r) return op[now];
	int mid=(l+r)/2;
	long long ans=tag[now]*(sum[y]-sum[x-1]);
	if(y<=mid) return gas(ls[now],x,y,l,mid)+ans;
	else if(mid<x) return gas(rs[now],x,y,mid+1,r)+ans;
	else return gas(ls[now],x,mid,l,mid)+gas(rs[now],mid+1,y,mid+1,r)+ans;
}

long long solve(int l,int r,int x){
	long long ans=dep[x]*(r-l+1)+tot[r]-tot[l-1];
	for(int i=0;i<V[x].size();i++)
		ans=ans-2*(gas(rt[r],V[x][i].first,V[x][i].second)-gas(rt[l-1],V[x][i].first,V[x][i].second));
	return ans;
}

void change(int x){
	swap(p[x],p[x+1]);
	tot[x]=tot[x-1]+dep[p[x]];
	if(T<=2e7){
		rt[x]=rt[x-1];
		for(int j=0;j<V[p[x]].size();j++)
			ins(rt[x],rt[x],V[p[x]][j].first,V[p[x]][j].second);
	}
	else{
		T=0;
		for(int i=1;i<=n;i++){
			rt[i]=rt[i-1];
			for(int j=0;j<V[p[i]].size();j++)
				ins(rt[i],rt[i],V[p[i]][j].first,V[p[i]][j].second);
		}
	}
}

int main(){
	scanf("%d %d",&n,&q);
	int ty,x,y,c;
	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
	for(int i=1;i<n;i++) scanf("%d %d %d",&x,&y,&c),ins(x,y,c),ins(y,x,c);
	dfs(1);dfs_2(1,1);
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
	for(int i=1;i<=n;i++) tot[i]=tot[i-1]+dep[p[i]];
	for(int i=1;i<=n;i++) got(i);
	for(int i=1;i<=n;i++){
		rt[i]=rt[i-1];
		for(int j=0;j<V[p[i]].size();j++)
			ins(rt[i],rt[i],V[p[i]][j].first,V[p[i]][j].second);
	}
	long long las=0,op=(1ll<<30);
	while(q--){
		scanf("%d %d",&ty,&x);x^=las;
		if(ty==1){
			scanf("%d %d",&y,&c);
			y^=las;c^=las;
			printf("%lld\n",las=solve(x,y,c));
			las%=op;
		}
		else change(x);
	}
}