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;

// #warning TODO, test various BLOCK SIZE and submit with 300
const int BLOCK_SIZE = 200;
const int MAX_N = 1e5 + 5;
// 0 1 2 3 4 | 5 6 7 8 9 | 10 ...
int plb[MAX_N];
int parent[MAX_N];
const int COUNT_BLOCKS = MAX_N/BLOCK_SIZE+1;
int offset[COUNT_BLOCKS];
set<int> with_parent_inside[COUNT_BLOCKS];

int get_block(int i) {
	return i / BLOCK_SIZE;
}
bool same_block(int i, int j) {
	return get_block(i) == get_block(j);
}

int get_parent(int i) {
	return max(1, parent[i] - offset[get_block(i)]);
}
bool parent_in_same_block(int i) {
	return same_block(i, get_parent(i));
}
int get_plb(int i) {
	if(parent_in_same_block(i)) {
		return plb[i];
	}
	else {
		return get_parent(i);
	}
}

int main() {
	int n, q;
	cin >> n >> q;
	// #warning TODO, pomysl o pozycji 0
	parent[1] = 0;
	for(int i = 2; i <= n; ++i) {
		cin >> parent[i];
		if(parent_in_same_block(i)) {
			plb[i] = get_plb(parent[i]);
		}
	}
	for(int i = 1; i <= n; ++i) {
		with_parent_inside[get_block(i)].insert(i);
	}
	// for(int i = 1; i <= n; ++i) {
		// cerr << get_plb(i) << " ";
	// }
	// cerr << endl;
	while(q--) {
		int type;
		cin >> type;
		if(type == 1) {
			// decrease
			int L, R, diff;
			cin >> L >> R >> diff;
			// 1) zielony
			if(!same_block(L, R)) {
				for(int i = L; i <= R && same_block(i, L); ++i) {
					parent[i] -= diff;
					parent[i] = max(parent[i], -100);
					if(parent_in_same_block(i)) {
						plb[i] = get_plb(get_parent(i));
					}
				}
			}
			// 2) zolte pelne
			for(int b = get_block(L) + 1; b < get_block(R); b++) {
				offset[b] += diff;
				offset[b] = min(offset[b], n);
				vector<int> to_erase;
				for(int i : with_parent_inside[b]) {
				// #warning TODO, zmien na seta
				// for(int i = b * BLOCK_SIZE; i < (b + 1) * BLOCK_SIZE; ++i) {
					if(parent_in_same_block(i)) {
						plb[i] = get_plb(get_parent(i));
					}
					else {
						to_erase.push_back(i);
					}
				}
				for(int i : to_erase) {
					with_parent_inside[b].erase(i);
				}
			}
			// 3) czerwony
			// if(!same_block(L, R)) {
			for(int i = max(L, R / BLOCK_SIZE * BLOCK_SIZE);
					i <= n && same_block(i, R); ++i) {
				if(i <= R) {
					parent[i] -= diff;
					parent[i] = max(parent[i], -100);
				}
				if(parent_in_same_block(i)) {
					plb[i] = get_plb(get_parent(i));
				}
			}
			// }
		}
		else {
			// LCA
			int x, y;
			cin >> x >> y;
			// for(int i = 1; i <= n; ++i) {
				// cerr << get_parent(i) << " ";
			// }
			// cerr << endl;
			// for(int i = 1; i <= n; ++i) {
				// cerr << get_plb(i) << " ";
			// }
			// cerr << endl;
			while(get_plb(x) != get_plb(y)) {
				if(x > y) {
					swap(x, y);
				}
				y = get_plb(y);
			}
			// cerr << x << " vs. " << y << endl;
			while(x != y) { // O(sqrt(N))
				if(x > y) {
					swap(x, y);
				}
				y = get_parent(y);
			}
			cout << x << "\n";
		}
		// #warning TODO, usun to przy submicie
		// for(int i = 0; i < BLOCK_SIZE; ++i) {
			// assert(plb[i] == 0);
			// assert(get_plb(i) == 0);
		// }
	}
}