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<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=1e5+10,maxs=350;
	int S,n,N,q,a[maxn],out[maxn],bel[maxn],tag[maxs],cnt[maxs],L[maxs],R[maxs];
	inline void sodu(int x){
		for(int i=L[x];i<=R[x];i++) a[i]=max(a[i]-tag[x],1);tag[x]=0;
		for(int i=L[x];i<=R[x];i++) if(a[i]<L[x]) out[i]=a[i];else out[i]=out[a[i]];
	}
	inline int to(int x){return max(1,out[x]-tag[bel[x]]);}
	inline int to2(int x){return x==1?0:max(1,a[x]-tag[bel[x]]);}
	inline void work(){
		n=read(),q=read();
		S=sqrt(n);
		a[1]=1;
		for(int i=2;i<=n;i++) a[i]=read(),bel[i]=(i-1)/S+1;
		N=bel[n];
		for(int i=1;i<=N;i++) L[i]=(i-1)*S+1,R[i]=min(n,i*S),sodu(i);
		while(q--) if(read()==1){
			int l=read(),r=read(),x=read(),bl=bel[l],br=bel[r];
			if(bl==br){
				for(int i=l;i<=r;i++) a[i]=max(1,a[i]-x);sodu(bl);
			}else{
				for(int i=bl+1;i<br;i++) {
					tag[i]=min(n,tag[i]+x);
					if(++cnt[i]<=S)sodu(i);
				}
				for(int i=l;i<=R[bl];i++) a[i]=max(1,a[i]-x);sodu(bl);
				for(int i=L[br];i<=r;i++) a[i]=max(1,a[i]-x);sodu(br);
			}
		}else{
		/*	int u=read(),v=read();
			while(to(u)!=to(v)){
				if(to(u)>to(v)) swap(u,v);
				v=to(v);
			}
			while(u!=v) if(to2(u)<to2(v)) v=to2(v);else u=to2(u);
			printf("%d\n",u);*/
			int x=read(),y=read();
				while(1){
				if(bel[x] < bel[y]) swap(x, y);
				if(bel[x] != bel[y]) x = to(x);
				else{
					if(to(x) != to(y)) x = to(x), y = to(y);
					else break;
				}
			}
			while(x != y){
				if(x < y) swap(x, y);
				x = max(1, a[x] - tag[bel[x]]);
			}
			printf("%d\n",x);
		}
	}
}
signed main(){
	star::work();
	return 0;
}