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<algorithm>
#include<iostream>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<bitset>
#include<cstdio>
#include<string>
#include<time.h>
#include<vector>
#include<cmath>
#include<deque>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N=1e5+5,B=320;
int a[N],b[N],c[B],lz[B],f;
int fk(int x)
{
	return (x+f-1)/f;
}
int main()
{
	int n,q,l,r,x,t,d,e;
	scanf("%d%d",&n,&q);
	f=sqrt((double)n);
	for(int i=2;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i+=f)
		for(int j=i;j<min(i+f,n+1);j++)
			if(a[j]<i)
				b[j]=a[j];
			else
				b[j]=b[a[j]];
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&t,&l,&r);
		if(t==1)
		{
			scanf("%d",&x);
			d=fk(l);
			e=fk(r);
			for(int j=d+1;j<e;j++)
				if(c[j]<f)
				{
					for(int k=(j-1)*f+1;k<=j*f;k++)
					{
						a[k]=max(a[k]-x,1);
						if(max(a[k]-lz[j],1)<=(j-1)*f)
							b[k]=max(a[k]-lz[j],1);
						else
							b[k]=b[max(a[k]-lz[j],1)];
					}
					c[j]+=min(x,f);
				}
				else
					lz[j]=min(lz[j]+x,n);
			for(int j=l;j<=min(d*f,r);j++)
			{
				a[j]=max(a[j]-x,1);
				if(max(a[j]-lz[fk(j)],1)<=(d-1)*f)
					b[j]=max(a[j]-lz[fk(j)],1);
				else
					b[j]=b[max(a[j]-lz[fk(j)],1)];
			}
			if(d!=e)
				for(int j=(e-1)*f+1;j<=r;j++)
				{
					a[j]=max(a[j]-x,1);
					if(max(a[j]-lz[fk(j)],1)<=(e-1)*f)
						b[j]=max(a[j]-lz[fk(j)],1);
					else
						b[j]=b[max(a[j]-lz[fk(j)],1)];
				}
			for(int j=r+1;j<=min(e*f,n);j++)
				if(max(a[j]-lz[fk(j)],1)<=(e-1)*f)
					b[j]=max(a[j]-lz[fk(j)],1);
				else
					b[j]=b[max(a[j]-lz[fk(j)],1)];
		}
		else
		{
			while(l!=r)
			{
				d=fk(l);
				e=fk(r);
				if(c[d]>=f)
					b[l]=max(a[l]-lz[d],1);
				if(c[e]>=f)
					b[r]=max(a[r]-lz[e],1);
				if(d==e)
					if(b[l]!=b[r])
						l=b[l],r=b[r];
					else
					{
						if(r>l)
							r=max(a[r]-lz[fk(r)],1);
						else
							l=max(a[l]-lz[fk(l)],1);
					}
				else
					if(d>e)
						l=b[l];
					else
						r=b[r];
			}
			printf("%d\n",l);
		}
	}
}