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<bits/stdc++.h>
using namespace std;
int n,m,top[100010],deln[320],tag[320],belong[100010],bl[320],br[320],fa[100010],bs;
#define gtlf(x) ((x-1)*bs+1)
#define gtrg(x) (min(x*bs,n))
void updtop(int x)
{
	if(belong[x]^belong[fa[x]])	top[x]=fa[x];
	else	top[x]=top[fa[x]];
}
void turndown(int x)
{
	if(tag[x])
	{
		for(int i=gtlf(x);i<=gtrg(x);++i)	fa[i]=max(fa[i]-tag[x],1);
		tag[x]=0;
	}
}
#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )
#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )
inline int rint() {
	int x = 0, f = 1, s = getchar();
	for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;
	for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
	return x * f;
}
template<typename Tp>
inline void wint( Tp x ) {
	if ( x < 0 ) putchar( '-' ), x = -x;
	if ( 9 < x ) wint( x / 10 );
	putchar( x % 10 ^ '0' );
}
#define utop( i ) ( top[i] = belong[fa[i]] != belong[i] ? fa[i] : top[fa[i]] )
#define gpar( i ) ( turndown( belong[i] ), fa[i] )
#define gtop( i ) ( deln[belong[i]] >= bs ? turndown( belong[i] ), fa[i] : top[i] )
int main() {
	scanf("%d %d",&n,&m),bs=sqrt(double(n))+1,fa[1]=belong[1]=1;
	for(int i=2;i<=n;++i)	scanf("%d",&fa[i]);
	for(int i=2;i<=n;++i)	belong[i]=(i-1)/bs+1,updtop(i);
	for ( int op, u, v; m--; ) {
		op = rint();
		if ( op & 1 )
		{
			int opl = rint(), opr = rint(), opx = rint();
			turndown( belong[opl] );
			for ( int i = opl; belong[i] == belong[opl]; ++i ) {
				if ( i <= opr ) fa[i] = max( fa[i] - opx, 1 );
				utop( i );
			}
			if ( belong[opl] == belong[opr] ) continue ;
			rep ( i, belong[opl] + 1, belong[opr] - 1 ) {
				if ( deln[i] >= bs ) { tag[i] += opx; continue; }
				++deln[i];
				int bl = ( i - 1 ) * bs + 1, br = min( i * bs, n );
				rep ( j, bl, br ) fa[j] = max( fa[j] - opx, 1 ), utop( j );
			}
			turndown( belong[opr] );
			for ( int i = ( belong[opr] - 1 ) * bs + 1; belong[i] == belong[opr]; ++i ) {
				if ( i <= opr ) fa[i] = max( fa[i] - opx, 1 );
				utop( i );
			}
		}
		else
		{
			int opx = rint(), opy = rint();
			while ( opx != opy ) {
				int tu = gtop( opx ), tv = gtop( opy );
				if ( belong[opx] != belong[opy] ) belong[opx] > belong[opy] ? opx = tu : opy = tv;
				else if ( tu != tv ) opx = tu, opy = tv;
				else opx > opy ? opx = gpar( opx ) : opy = gpar( opy );
			}
			printf("%d\n", opx);
		}
	}
	return 0;
}