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;

template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; }
template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }

#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int, int> PR;
typedef vector<int> VI; 

const lod eps = 1e-9;
const lod pi = acos(-1);
const int oo = 1 << 30;
const ll loo = 1ll << 60;
const int mods = 998244353;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f; //1061109567
/*--------------------------------------------------------------------*/

namespace FastIO{
	constexpr int SIZE = (1 << 21) + 1;
	int num = 0, f;
	char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf, *oT = obuf + SIZE - 1, c;
	#define gc() (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	inline void putc(char c) {
		*oS ++ = c;
		if (oS == oT) flush();
	}
	inline void getc(char &c) {
		for (c = gc(); (c < 'a' || c > 'z') && c != EOF; c = gc());
	}
	inline void reads(char *st) {
		char c;
		int n = 0;
		getc(st[++ n]);
		for (c = gc(); c >= 'a' && c <= 'z' ; c = gc()) st[++ n] = c;
	}
	template<class I>
	inline void read(I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9' ; c = gc()) if (c == '-') f = -1;
		for (x = 0; c >= '0' && c <= '9' ; c = gc()) x = (x << 3) + (x << 1) + (c & 15);
		x *= f;
	}
	template<class I>
	inline void print(I x) {
		if (x < 0) putc('-'), x = -x;
		if (!x) putc('0');
		while (x) que[++ num] = x % 10 + 48, x /= 10;
		while (num) putc(que[num --]);
	}
	struct Flusher_{~Flusher_(){flush();}} io_Flusher_;
}
using FastIO :: read;
using FastIO :: putc;
using FastIO :: reads;
using FastIO :: print;


int tag[MAXN], flag[MAXN], a[MAXN], bel[MAXN], L[MAXN], R[MAXN], bfa[MAXN], nxtb[MAXN], sz, n, Case, lst = 0;
void rebuild(int x) {
	upmin(tag[x], n);
	if (flag[x]) return;
	flag[x] = 1;	
	for (int i = L[x]; i <= R[x] ; ++ i) {
		a[i] = max(a[i] - tag[x], 0);
		nxtb[i] = (a[i] < L[x] ? a[i] : nxtb[a[i]]);
		bfa[i] = (a[i] < L[x] ? i : bfa[a[i]]);
		flag[x] &= (a[i] < L[x]);	
	}
	tag[x] = 0;
}
signed main() {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif 
	read(n), read(Case), sz = (int)sqrt(n);
	for (int i = 2; i <= n ; ++ i) read(a[i]);
	for (int i = 1; i <= n ; ++ i) bel[i] = (i - 1) / sz + 1;
	for (int i = 1; i <= bel[n] ; ++ i) L[i] = (i - 1) * sz + 1, R[i] = min(i * sz, n), rebuild(i);
	while (Case --) {
		int opt, x, y, z;
		read(opt);
		if (opt == 1) {
			read(x), read(y), read(z), x ^= lst, y ^= lst, z ^= lst;
			if (bel[x] == bel[y]) {
				for (int i = x; i <= y ; ++ i) a[i] = max(a[i] - z, 0);
				rebuild(bel[x]);
				continue;
			}
			for (int i = x; i <= R[bel[x]] ; ++ i) a[i] = max(a[i] - z, 0);
			for (int i = bel[x] + 1; i <= bel[y] - 1 ; ++ i) tag[i] += z;
			for (int i = L[bel[y]]; i <= y ; ++ i) a[i] = max(a[i] - z, 0);
			for (int i = bel[x]; i <= bel[y] ; ++ i) rebuild(i);
		}
		else {
			read(x), read(y), x ^= lst, y ^= lst;
			for (; ;) {
				while (bel[x] != bel[y]) {
					if (x < y) swap(x, y);
					x = (flag[bel[x]] ? max(a[x] - tag[bel[x]], 1) : max(nxtb[x], 1));
				}
				if (bfa[x] != bfa[y]) {
					x = (flag[bel[x]] ? max(a[x] - tag[bel[x]], 1) : max(nxtb[x], 1));
					y = (flag[bel[y]] ? max(a[y] - tag[bel[y]], 1) : max(nxtb[y], 1));
				}
				else break;
			}
			while (x != y) {
				if (x < y) swap(x, y);
				x = max(a[x] - tag[bel[x]], 1);
			}
			print(x), putc('\n');
		}
	}
	return 0;
}