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 ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define mp make_pair
#define pi pair<int, int>
#define pb push_back
#define vi vector<int>
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 2e5 + 5 ; 
const int M = 500 ; 
int n, m, cnt, a[N], Id[N], tag[N], L[N], R[N] ; 
int pre[N], ll[N] ; 
void Add(int l, int r, int x) {
	if(Id[l] == Id[r]) rep( i, l, r ) a[i] -= x ; 
	else {
		for(int i = l; i <= R[Id[l]]; ++ i) a[i] -= x ;
		for(int i = Id[l] + 1; i < Id[r]; ++ i) tag[i] -= x ; 
		for(int i = L[Id[r]]; i <= r; ++ i) a[i] -= x ; 
	}
}
int qry(int x) { return max(1ll, a[x] + tag[Id[x]]) ; }
int Get(int x) {
	int g = qry(x) ; 
	if(g == 1) return 1 ; 
	return (g < ll[x]) ? g : pre[x] ;
}
set<int> S ; 
set<int>::iterator it ; 
void Rebuild(int x) {
	for(int i = L[x]; i <= R[x]; ++ i) {
		if(qry(i) < ll[i]) pre[i] = qry(i) ; 
		else pre[i] = Get(qry(i)) ;  
	}
}
signed main()
{
	n = gi(), m = gi(), cnt = sqrt(n) + 1 ; 
	rep( i, 2, n ) a[i] = gi() ; 
	int idx = 0 ; L[++ idx] = 1 ; 
	rep( i, 1, n ) {
		Id[i] = idx ; 
		if(!(i % cnt)) R[idx] = i, L[++ idx] = i + 1 ; 
	} R[idx] = n ; pre[1] = 1 ; 
	rep( i, 2, n ) {
		int u = L[Id[i]] ; ll[i] = u ; 
		if(a[i] < u) pre[i] = a[i] ;
		else pre[i] = pre[a[i]], S.insert((int)i) ; 
	} 
	rep( i, 1, m ) {
		int opt = gi(), l = gi(), r = gi() ; 
		if(opt == 1) {
			int x = gi() ; Add(l, r, x) ; 
			if(!S.empty()) {	
				it = S.lower_bound(l) ; 
				vector<int> del ; 
				for(; it != S.end(); ++ it) {
					int u = (*it) ; 
					if(u > r) break ; 
					int d = qry(u) ; 
					if(d < ll[u]) del.pb(u) ; 
					else pre[u] = Get(d) ; 
				}
				for(int v : del) S.erase(v) ; 
				Rebuild(Id[l]), Rebuild(Id[r]) ; 
			}
		} else {
			int u = l, v = r ; 
			while(Get(u) != Get(v)) {
			//	printf("now case %d %d %d %d\n", u, v, Get(u), Get(v)) ; 
				if(Get(u) < Get(v)) swap(u, v) ; 
				u = Get(u) ; 
			}
			while(u != v) {
				if(u < v) swap(u, v) ; 
				u = qry(u) ; 
			}
			printf("%lld\n", u ) ; 
		}
	}
	return 0 ;
}