Problem: Yuezheng Ling gives Luo Tianyi a tree which has n nodes, rooted at 1. 

Luo Tianyi will tell you that the parent of the i-th node is a_i (1 ≤ a_i<i for 2 ≤ i ≤ n), and she will ask you to perform q queries of 2 types:

  1. She'll give you three integers l, r and x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5). You need to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.
  2. She'll give you two integers u, v (1 ≤ u, v ≤ n). You need to find the [LCA](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of nodes u and v (their lowest common ancestor).

Input

The first line contains two integers n and q (2≤ n,q ≤ 10^5) — the number of nodes and the number of queries, respectively.

The second line contains n-1 integers a_2, a_3,..., a_n (1 ≤ a_i < i), where a_i is the parent of the node i.

Next q lines contain queries. For each query, the first integer of each line is t (t = 1 or 2) — the type of the query. 

If t = 1, this represents the query of the first type. Then, three integers will follow: l, r, x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5), meaning that you have to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.

If t = 2, this represents the query of the second type. Then, two integers will follow: u and v (1 ≤ u, v ≤ n), and you have to find the LCA of u and v. 

It's guaranteed that there is at least one query of the second type.

Output

For each query of the second type output answer on a new line.

Example

Input


6 4
1 2 3 3 4
2 3 4
1 2 3 1
2 5 6
2 2 3


Output


3
3
1

Note

The tree in example is shown below.

<image>

After the query of the first type, the tree changes and is looking as shown below.

<image>

Solution (in CPP):

Solution:
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#include <cstdio>
#include <cmath>

typedef long long ll;
const int maxn = 4e5 + 5 ,S = 675 ;

template<typename T>
inline T max(const T &a,const T &b){
	return a>b?a:b;
}

template<typename T>
inline void swap(T &a,T &b){
	T tmp = a;a = b;b = tmp;
}

template<typename T>
inline T min(const T &a,const T &b){
	return a<b?a:b;
}

struct IO{
	static const int maxn = 2e5 + 5;
	char c;
	inline char gc(){
		static char buf[maxn],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
	}
	template<typename T>
	inline IO&operator>>(T &_){
		_=0;bool f=1;c=gc();while(c<'0'||c>'9'){if(c=='-') f=0; c=gc();}
		while(c>='0'&&c<='9'){_=_*10+c-48;c=gc();}if(!f) _=-_;return *this;
	}
	char buf[maxn];int p = 0;~IO(){fwrite(buf,1,p,stdout);}
	inline void pc(const char &c){
		buf[p++] = c;
		if(p==maxn) fwrite(buf,1,maxn,stdout),p=0;
	}
	template<typename T>
	inline IO&operator<<(T x){
		if(!x){pc(48);pc('\n');return *this;}static int wt[41],len;len=0;if(x<0){pc('-');x=-x;}
		for(;x;x/=10){wt[++len]=x%10;}
		while(len){pc(wt[len--]+48);}pc('\n');return *this;
	}
}io;

int n,m,block_size,f[maxn];int a[maxn],tag[S];int phi[S];

inline int where(int x){return (x-1)/block_size+1 ;}

inline int L(int id){return (id-1)*block_size+1;}
inline int R(int id){return min(id*block_size,n);}

inline int trans(int x){return max(a[x]-tag[where(x)],1);}

inline int Trans(int x){
	if(phi[where(x)]>=S) return trans(x) ;
	return f[x] ;
}

void rebuild(int id){
	if(phi[id]>=S) return ;
	phi[id] ++ ;
	bool Dirty_Deeds_Done_Dirt_Cheap = 1;
	for(int i=L(id);i<=R(id);i++){
		if(where(i)!=where(trans(i))) f[i] = trans(i);
		else
			f[i] = Trans(trans(i)) ,Dirty_Deeds_Done_Dirt_Cheap = 0;
	}
	if(Dirty_Deeds_Done_Dirt_Cheap) phi[id] = S;
}

void init(){
	block_size = sqrt(n) + 21;
	f[1] = a[1] = 1;
	for(int i=1;i<=where(n);i++)
		rebuild(i);
}

int Pepper(int u,int v){
	while(Trans(u)!=Trans(v) && u!=1){
		if(Trans(u)<Trans(v)) swap(u,v);
		u = Trans(u);
	}
	while(trans(u)!=trans(v) && u!=1){
		if(u<v) swap(u,v);
		u = trans(u);
	}
	return u==v?u:trans(u) ;
}

void modify(int l,int r,const int &key){
	int idl = where(l) , idr = where(r) ;
	if(idl==idr){
		for(int i=l;i<=r;i++) a[i] = max(1,a[i]-key);
		return rebuild(idl) ;
	}
	for(int i=l;i<=R(idl);i++) a[i] = max(1,a[i]-key);
	rebuild(idl);
	for(int i=L(idr);i<=r;i++) a[i] = max(1,a[i]-key);
	rebuild(idr);
	for(int i=idl+1;i<idr;i++){
		tag[i] = min(n,tag[i]+key);
		rebuild(i) ;
	}
}

int main(){
	scanf("%d%d",&n,&m);for(int i=2;i<=n;i++) io>>a[i];
	init();
	int lans = 0;
	while(m--){
		int type ;io>>type;
		if(type == 1){
			int l,r,key;io>>l>>r>>key;//l^=lans,r^=lans,key^=lans;
			modify(l,r,key);
		}
		if(type == 2){
			int u,v;io>>u>>v;
// 			u^=lans, v^=lans;
			io << (lans = Pepper(u,v));
		}
	}
	return 0 ;
}