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:
#include <cstdio>

typedef long long ll;
const int maxn = 1e5 + 5 , S = 375 ;

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;
}

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

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

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

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

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 ;
	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));
	}
}

void init(){
	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(trans(u)<trans(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] -= key;
		return rebuild(idl) ;
	}
	for(int i=l;i<=R(idl);i++) a[i] -= key;
	rebuild(idl);
	for(int i=L(idr);i<=r;i++) a[i] -= key;
	rebuild(idr);
	for(int i=idl+1;i<idr;i++){
		tag[i] += key;
		if(phi[i]<S)
			rebuild(i),phi[i] ++ ;
	}
}

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