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:
/*
思路：弹飞绵羊暴力分块： 
修改：整块直接改，边角块重构好欸          
查询：前后指针，大块直接跳然后块内并查集查询
重构：分为两种，一种边角块重构~~这是算在修改里面的~~没有影响，而另一种重构是属于有点到根节点1的重构，一个块只有\sqrt_n的元素所以重构至多n次，而一次重构就\sqrt n的时间复杂度所以这一块时间复杂度我们不会爆炸 
注意并查集里面维护的是在同一个块里面的点
我们重新理一下思路：我们并查集里面维护的相当于是还在这一个块里面的情况对吧，离开了这个块最好，所以我们没有错！！！ 
被讨论区带了波节奏：对于一个超过了根号次的块直接走就好了…… 
被一个毒瘤点卡RE了 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
const int Len = 1e6 + 5 , SIZE = 15000;
int t,n,m,L[SIZE],R[SIZE],pos[Len],siz[SIZE],fa[Len],a[Len],Del[SIZE],tot[SIZE];
inline void makeSet(int l,int r){for(int i = l ; i <= r ; i ++) fa[i] = i;}
inline int findSet(int x){return fa[x] == x ? fa[x] : fa[x] = findSet(fa[x]);}
inline void unionSet(int x,int y)
{
	int u = findSet(x) , v = findSet(y);
	if(u == v) return;
	fa[v] = u;
}
inline void maintain(int Blk)
{
	makeSet(L[Blk] , R[Blk]);
	for(int j = L[Blk] ; j <= R[Blk] ; j ++) if(pos[a[j]] == Blk) unionSet(a[j] , j);
}
inline void DDel(int Blk,int x)
{
	tot[Blk] += x;
	for(int j = L[Blk] ; j <= R[Blk] ; j ++) a[j] = max(a[j] - x , 1LL);
	makeSet(L[Blk] , R[Blk]);
	for(int j = L[Blk] ; j <= R[Blk] ; j ++) if(pos[a[j]] == Blk) unionSet(a[j] , j);
}
signed main()
{
	scanf("%lld %lld",&n,&m);
	a[0] = 1;
	a[1] = 0;
	pos[0] = 1;
	for(int i = 2 ; i <= n ; i ++) scanf("%lld",&a[i]);
	t = sqrt(n);
	for(int i = 1 ; i <= t ; i ++) L[i] = (i - 1) * t + 1 , R[i] = i * t , siz[i] = R[i] - L[i] + 1;
	if(R[t] != n)
	{
		t ++;
		L[t] = R[t - 1] + 1;
		R[t] = n;
		siz[t] = R[t] - L[t] + 1;
	}
	for(int i = 1 ; i <= t ; i ++)
	{
		tot[i] = 0;
		makeSet(L[i] , R[i]);
		for(int j = L[i] ; j <= R[i] ; j ++) pos[j] = i;
		for(int j = L[i] ; j <= R[i] ; j ++) if(pos[a[j]] == i) unionSet(a[j] , j);
	}
	int lstans = 0;
	while(m --)
	{
		//for(int i = 1 ; i <= n ; i ++) printf("%d\n",a[i] - Del[pos[i]]);
		int opt;scanf("%lld",&opt);
		if(opt == 1)
		{
			int l,r,x;scanf("%lld %lld %lld",&l,&r,&x);
			//l ^= lstans , r ^= lstans , x ^= lstans;
			//if(l > r) swap(l , r);
			int Ll = pos[l] , Rr = pos[r];
			if(Ll == Rr) 
			{
				for(int i = l ; i <= r ; i ++) a[i] = max(a[i] - x , 1LL);
				if(tot[Ll] < siz[Ll]) maintain(Ll);
				continue;
			}
			for(int i = Ll + 1 ; i <= Rr - 1 ; i ++)
			{
				if(tot[i] >= siz[i]) Del[i] += x;
				else DDel(i , x);
			}
			for(int i = l ; i <= R[Ll] ; i ++) a[i] = max(a[i] - x , 1LL);
			if(tot[Ll] < siz[Ll]) maintain(Ll);
			for(int i = L[Rr] ; i <= r ; i ++) a[i] = max(a[i] - x , 1LL);
			if(tot[Rr] < siz[Rr]) maintain(Rr);
		}
		else
		{
			int u,v;scanf("%lld %lld",&u,&v);
			//u ^= lstans , v ^= lstans;
			bool flag = false;
			while(u != 1 && v != 1)
			{
				if(pos[u] == pos[v])
				{
					if(tot[pos[u]] >= siz[pos[u]])
					{
						if(u == v)
						{
							lstans = u;
							printf("%lld\n",u);
							flag |= 1;
							break;
						}
						//否则一定在这个块内没有答案 
						u = max(1LL , a[u] - Del[pos[u]]);
						v = max(1LL , a[v] - Del[pos[v]]);
					}
					else
					{
						if(findSet(u) == findSet(v))//表明答案就在这个块内 
						{
							while(u != v)
							{
								if(u > v) swap(u , v);
								v = max(1LL , a[v] - Del[pos[v]]);
							}
							lstans = u;
							printf("%lld\n",u);
							flag |= 1;
							break;
						}
						else 
						{
							u = max(1LL , a[findSet(u)] - Del[pos[u]]);
							v = max(1LL , a[findSet(v)] - Del[pos[v]]);
						}
					}
 				}
 				else
 				{
					if(u > v) swap(u , v);
					if(tot[pos[v]] >= siz[pos[v]]) v = max(1LL , a[v] - Del[pos[v]]);
					else v = max(1LL , a[findSet(v)] - Del[pos[v]]);
				}
			}
			if(!flag){lstans = 1;printf("1\n");}
		}
	}
	return 0;
}