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:
//Common Header Simple over C++11
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define STLsz(x) ((int)(x).size())
#define memset0(x) memset((x),0,sizeof(x));
//#define endl '\n'
#define count2(x) __builtin_popcount(x)
#define countleadingzero(x) __builtin_clz(x)
#define dd(x) cerr << #x << " = " << x << ' ';
#define de(x) cerr << #x << " = " << x << endl;
//inline char nc() {
//  static char buf[1000000], *p = buf, *q = buf;
//  return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
//             ? EOF
//             : *p++;
//}
inline ll rd(){//LLONG_MIN LMAX=9,223,372,036,854,775,807
	ll s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	//这个提交学习自 https://codeforces.com/contest/1491/submission/108742524
	// 题意 给一个n个节点的树 告诉你每个节点i的父亲ai ai<i q个询问 有两个操作 一个是对l-r区间的节点的父亲取max(ai-x,1) 一个是对u,v询问两个节点的最近公共祖先 
	/* 
	Editor: INFINT
	Time: 2021-03-06 
	Solution:复杂度 nsqrt(n)+qsqrt(n) 
	见注释 
	*/
	int n,q;
	cin>>n>>q;
	
	const int MAGIC=sqrt(n); //块大小 
	const int BLOCKS=n/MAGIC+1; //块数 
	vector<int>tree(n,0);
	vector<int>leave_block(n,0);
	vector<int>add(BLOCKS);
	vector<int>cnt(BLOCKS);
	
	auto recalc=[&](int block){
		for(int i=block*MAGIC;i<min(n,(block+1)*MAGIC);++i)	tree[i]=max(0,tree[i]-add[block]);
		add[block]=0;
		for(int i=block*MAGIC;i<min(n,(block+1)*MAGIC);++i){
			int W=tree[i]; //将这个节点的父亲保存到W 
			if(W<block*MAGIC)leave_block[i]=W; //这个节点的父亲是W W在块外 
			else leave_block[i]=leave_block[W]; //这个节点的父亲是块内的某个块的第一个在块外的父亲 
		}
	};
	
	for(int i=1;i<n;++i)cin>>tree[i],tree[i]--;
	
	for(int i=0;i*MAGIC<n;++i) recalc(i); //计算每一块
	/*
	图1 
 	        l     r     
	[    ][    ][    ][     ] 
	L1  R1L2  R2L3  R3L4   R4
	*/ 
	for(int qi=0,op,l,r,x,u,v;qi<q;++qi){//q个询问 
		cin>>op;
		if(op==1){
			cin>>l>>r>>x;
			l--,r--;
			for(int i=0;i*MAGIC<n;++i){
				int L=i*MAGIC,R=min(n,(i+1)*MAGIC)-1;
				int pl=max(L,l),pr=min(R,r);// 对于每一个当前枚举的块 考虑和请求更新的边界的交集
				// pl是当前块的左端点和询问的左边界的较大者 就是块内需要修改的左端点 
				// pr是当前块的右端点和询问的右边界的较小者 就是块内需要修改的右端点 
				if(pl>pr)continue;// 说明这个块不在询问的影响范围内 可以通过画图1得知
				if(pl!=L||pr!=R||cnt[i]<=MAGIC){// 如果不是边界 或者修改的次数小于分块的大小 
					if(pl==L&&pr==R){// 这种情况说明 块的L和R恰好是询问的l和r 
						cnt[i]++;
						add[i]+=x;
						add[i]=min(add[i],n);
					}
					else{
						for(int e=pl;e<=pr;++e)tree[e]=max(0,tree[e]-x);
					}
					recalc(i);
				}
				else{// 当一个块修改超过分块次数的时候 直接打标记 
					add[i]+=x;
					add[i]=min(add[i],n);
				}
				 
			}
		}
		else{
			auto layer=[&](int x){return x/MAGIC;};// 返回所属的块号 
			auto go_outer=[&](int x){return max(0,leave_block[x]-add[layer(x)]);};// 返回所属的父亲
			auto go=[&](int x){return max(0,tree[x]-add[layer(x)]);};// 返回所属的父亲 
			cin>>u>>v;u--,v--;
			while(u!=v){
				if(layer(u)<layer(v))swap(u,v);// 如果u所属的块比v所属的块号大 交换
				if(layer(u)>layer(v)){
					u=go_outer(u); //按块跳跃 
				}
				else{// layer(u)==layer(v) 同一块 
					int A=go_outer(u),B=go_outer(v); 
					if(A!=B){
						u=A,v=B;
					} 
					else{
						while(u!=v){
							if(u>v)u=go(u);
							else v=go(v);
						}
					}
				}
			}
			cout<<u+1<<'\n';
		}
	} 
	return 0;
}