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>
#include<cstring> 
#include<cmath>
#define  N  110000
#define  SN  510
using  namespace  std;
int  pre[N];
int  lazy[SN];bool  by[SN];//用来存这个块内的点是不是都能一次指向块外，只有当这个为0时，ku才有用，否则都是用pre 
int  ku[N];//指向块外
int  block,be[N],ll[SN],rr[SN];
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
inline  void  zwap(int  &x,int  &y){x^=y^=x^=y;}
int  n,m;
inline  void  chuli(int  l,int  r)//把整个块给我输进来 
{
	if(by[be[l]]==1)return  ;
	bool  bk=0;
	for(int  i=l;i<=r;i++)
	{
		int  x=pre[i];
		if(x>=l)x=ku[x],bk=1;
		ku[i]=x;
	}
	if(!bk)by[be[l]]=1;
}
void  putlan(int  l,int  r,int  la)
{
	if(be[l-1]!=be[l]  &&  be[r+1]!=be[r]  &&  by[be[l]])
	{
		lazy[be[l]]+=la;//直接修改懒标记 
		if(lazy[be[l]]>n)lazy[be[l]]=n;
	}
	else
	{
		for(int  i=l;i<=r;i++)pre[i]=mymax(1,pre[i]-la);
		chuli(ll[be[l]],rr[be[r]]);
	}
}
int  findans(int  x,int  y)
{
	int  tx=x,ty=y;//分别记录的是之前的x 
	while(x!=y)
	{
		if(x<y)zwap(x,y),zwap(tx,ty);//让y始终大于x 
		tx=x;
		if(by[be[x]]==1)x=mymax(1,pre[x]-lazy[be[x]]);
		else  x=ku[x];//直接飞到块外 
	}
	//既然相等了，那么就考虑tx,ty一步步跳
	while(tx!=ty)
	{
		if(tx<ty)zwap(tx,ty);
		if(by[be[tx]]==1)tx=mymax(1,pre[tx]-lazy[be[tx]]);
		else  tx=pre[tx];//直接飞到块外 
	}
	return  tx;
}
void  change(int  l,int  r,int  val)
{
	if(be[l]==be[r])putlan(l,r,val);
	else
	{
		putlan(l,rr[be[l]],val);l=rr[be[l]]+1;
		putlan(ll[be[r]],r,val);r=ll[be[r]]-1;
		while(l<=r)putlan(l,rr[be[l]],val),l=rr[be[l]]+1;
	}
}
int  main()
{
	scanf("%d%d",&n,&m);
	pre[1]=1;for(int  i=2;i<=n;i++)scanf("%d",&pre[i]);
	block=sqrt(n);
	for(int  i=1;i<=n;i++)be[i]=(i-1)/block+1;
	if(be[1]==be[2])
	{
		for(int  i=2;i<=n;i++)be[i]++;//把1孤立成一个块 
	}
	for(int  i=1;i<=n;i++)
	{
		if(be[i]!=be[i-1])ll[be[i]]=i;
		rr[be[i]]=i;
	}
	for(int  i=1;i<=be[n];i++)chuli(ll[i],rr[i]);
	by[1]=1;
	for(int  i=1;i<=m;i++)
	{
		int  type;scanf("%d",&type);
		if(type==1)
		{
			int  l,r,v;scanf("%d%d%d",&l,&r,&v);
			change(l,r,v);
		}
		else
		{
			int  x,y;scanf("%d%d",&x,&y);
			printf("%d\n",findans(x,y));
		}
	}
	return  0;
}