卡到60pts硬是卡不动了（）

#include<bits/stdc++.h>
#define re register int
#define il inline
using namespace std;
const int N=4e5+10;
const int SQ=1010;
int fa[N],nx[N],n,m,op,lstans,kuai,k,x,y,chg[SQ];
long long tag[SQ];
il int read(){
	int xx=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}
	while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+(ch^48);ch=getchar();}
	return xx*f;
}
il void write(int x){
	if(x<10)putchar(x+'0');
	else{write(x/10);putchar(x%10+'0');}
}
il int NX(int u){
	if(chg[u/kuai]<=kuai)return nx[u];
	return max(1,(int)(fa[u]-tag[u/kuai]));
}
il int FA(int u){
	if(chg[u/kuai]<=kuai)return fa[u];
	return max(1,(int)(fa[u]-tag[u/kuai]));
}
int main(){
	n=read();m=read();
	kuai=650;
	for(re i=2;i<=n;i++)fa[i]=read();
	fa[1]=1;nx[1]=1;
	for(re i=2;i<=n;i++){
		if(fa[i]/kuai!=i/kuai)nx[i]=fa[i];
		else nx[i]=nx[fa[i]];
	}
	while(m--){
		op=read();x=read();y=read();
		x=x^lstans;y=y^lstans;
		if(op==1){
			k=read()^lstans;
			if((x/kuai)==(y/kuai)){//每一个块的界都是模它为0~kuai-1的  同块暴力改 
				for(re i=x;i<=y;i++)fa[i]=max(fa[i]-k,1);
				if(chg[x/kuai]<=kuai){
					for(re i=x;i<min((n+1),((y/kuai)+1)*kuai);i++){
						if((fa[i]/kuai)!=(i/kuai))nx[i]=fa[i];
						else nx[i]=nx[fa[i]];
					}
				}
			}
			else{
				int l=x,r=y;
				int z=min(n+1,(l/kuai)+1)*kuai;
				for(re i=l;i<z;i++)fa[i]=max(fa[i]-k,1);
				if(chg[l/kuai]<=kuai){
					for(re i=l;i<z;i++){
						if((fa[i]/kuai)!=(i/kuai))nx[i]=fa[i];
						else nx[i]=nx[fa[i]];
					}
				}
				for(re i=(r/kuai)*kuai;i<=r;i++)fa[i]=max(fa[i]-k,1);
				z=min((n+1),((r/kuai)+1)*kuai);
				if(chg[r/kuai]<=kuai){
					for(re i=(r/kuai)*kuai;i<z;i++){
						if((fa[i]/kuai)!=(i/kuai))nx[i]=fa[i];
						else nx[i]=nx[fa[i]];
					}
				}
				for(re i=(l/kuai)+1;i<r/kuai;i++){
					if(chg[i]<=kuai){
						z=min(n+1,(i+1)*kuai);
						for(re j=i*kuai;j<z;j++){
							fa[j]=max(fa[j]-k,1);
							if(chg[j/kuai]<=kuai){
								if((fa[j]/kuai)!=(j/kuai))nx[j]=fa[j];
								else nx[j]=nx[fa[j]];
							}
						}
					}
					else{tag[i]+=k;if(tag[i]>n)tag[i]=n;}
					if(chg[i]<=kuai)chg[i]+=k;
				}
			}
		}
		else{
			while(x!=y){
				int xx=NX(x),yy=NX(y);
				if((xx/kuai)!=(yy/kuai)){
					if((xx/kuai)<(yy/kuai))y=yy;
					else x=xx;
				}
				else{
					if(xx!=yy){
						if(xx<yy)y=yy;
						else x=xx;
					}
					else{
						if(x<y)y=FA(y);
						else x=FA(x);
					}
				}
			}
			lstans=x;write(lstans);
			putchar('\n');
		}
	}
}