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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = y; i >= x; --i)
#define repg(i, u) for(int i = head[u]; i; i = e[i].nxt)
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 100010, M = 350;
int n, m, k, p, opt, x, y, z, a[N], b[N], cnt[M], f[M], L[M], R[M], pos[N];
inline void update(int x){
	rep(i, L[x], R[x]) a[i] = max(1, a[i] - f[x]);
	f[x] = 0; rep(i, L[x], R[x]){
		if(a[i] < L[x]) b[i] = a[i];
		else b[i] = b[a[i]];
	}
}
inline void change(int x, int y, int z){
	int l = pos[x], r = pos[y];
	if(l == r){
		rep(i, x, y) a[i] = max(a[i] - z, 1);
		update(l); return;
	}
	rep(i, x, R[l]) a[i] = max(a[i] - z, 1); update(l);
	rep(i, L[r], y) a[i] = max(a[i] - z, 1); update(r);
	rep(i, l + 1, r - 1){
		++cnt[i]; f[i] = min(N, f[i] + z);
		if(cnt[i] <= k) update(i);
	}
}
inline int get_b(int x){ return max(1, b[x] - f[pos[x]]); }

inline int lca(int x, int y)
{
	while (get_b(x) != get_b(y) || pos[x] != pos[y])
	{
		if (pos[x] != pos[y])
		{
			if (pos[x] < pos[y]) swap(x, y);
			x = get_b(x);	
		}
		else
			x = get_b(x), y = get_b(y);
	}
	while (x != y)
	{
		if (x < y) swap(x, y);
		x = max(a[x]-f[pos[x]], 1);
	}
	return x;
}
inline void work(){
	n = read(); m = read(); k = sqrt(n); pos[1] = 1; p = (n - 1) / k + 1;
	rep(i, 2, n) a[i] = read(), pos[i] = (i - 1) / k + 1; 
	rep(i, 1, p) L[i] = (i - 1) * k + 1, R[i] = min(n, i * k);
	rep(i, 1, p) update(i); while(m--){
		opt = read(); x = read(); y = read();
		if(opt == 1) z = read(), change(x, y, z);
		else printf("%d\n", lca(x, y));
	}
}
int main(){ int qwq = 1; while(qwq--) work(); return 0; }