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 optimize("Ofast")
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define REP(u) for(int i=p[u];i!=-1;i=e[i].nxt)
#define PII pair<int,int>
#define ll long long
#define pb push_back
#define PLL pair<ll,ll>
#define fi first
#define A(x) ((x)%mod)
#define se second
#define sz(x) (int)(x.size())
#define rd (rand()<<16^rand())
#define gc (_p1==_p2&&(_p2=(_p1=_buf)+fread(_buf,1,100000,stdin),_p1==_p2)?EOF:*_p1++)
using namespace std;
char _buf[100000],*_p1=_buf,*_p2=_buf;
inline int gi()
{
	int x=0,f=1;
	char ch=gc;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=gc;
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc;
	}
	return (f==1)?x:-x;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int block=250,B=100000/block+1,maxn=1e5+5;
int n,q,fa[maxn],g[maxn],cnt[maxn],tag[maxn],tot;
int posl[maxn],posr[maxn],bel[maxn];
inline void init()
{

}
inline void input()
{
	n=gi(),q=gi();
	FOR(i,2,n)fa[i]=gi();
	FOR(i,1,n)bel[i]=(i-1)/block+1;
	tot=(n-1)/block+1;
	FOR(i,1,tot)posl[i]=posr[i-1]+1,posr[i]=min(n,posl[i]+block-1);
	FOR(i,1,n)bel[fa[i]]==bel[i]?g[i]=g[fa[i]]:g[i]=i;
}
inline void update(int l,int r,int x)
{
	FOR(i,l,r)fa[i]=max(fa[i]-x,1);
	l=posl[bel[l]],r=posr[bel[r]];
	FOR(i,l,r)fa[i]=max(fa[i]-tag[bel[l]],1);
	FOR(i,l,r)bel[fa[i]]==bel[i]?g[i]=g[fa[i]]:g[i]=i;
	tag[bel[l]]=0;
}
inline void change(int l,int r,int x)
{
	if(bel[l]==bel[r])update(l,r,x);
	else
	{
		int bl=bel[l],br=bel[r];
		update(l,posr[bl],x);
		update(posl[br],r,x);
		bl++,br--;
		FOR(i,bl,br)
		{
			if(cnt[i]<=B)
			{
				cnt[i]++;
				update(posl[i],posr[i],x);
			}
			else tag[i]+=x;
		}
	}
}
int counter=0;
inline int LCA(int u,int v)
{
	while(g[u]!=g[v])
	{
		counter++;
		if(u<v)swap(u,v);
		u=max(fa[g[u]]-tag[bel[u]],1);
	}
	while(u!=v)
	{
		counter++;
		if(u<v)swap(u,v);
		u=max(fa[u]-tag[bel[u]],1);
	}
	return u;
}
inline void solve()
{
	while(q--)
	{
		int t=gi();
		if(t==1)
		{
			//double st=clock();
			int l=gi(),r=gi(),x=gi();
			change(l,r,x);
			//cerr<<clock()-st<<endl;
		}
		else
		{
			int u=gi(),v=gi();
			printf("%d\n",LCA(u,v));
			//cerr<<counter<<endl;
		}
	}
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
//	int T=gi();
//	while(T--)
//	{
		init();
		input();
		solve();
//	}
	return 0;
}