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 <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 100005;
int n,q,k;
int pos[N],L[N],R[N],a[N],b[N],add[N];
int cnt[N];
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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

void change(int l,int r,int x) {
	int p = pos[l],q = pos[r];
	if(p == q) {
		for(int i = l;i <= r;i++) {
			a[i] = max(a[i]-x,1);
		}
		for(int i = L[p];i <= R[p];i++) a[i] = max(a[i]-add[p],1);
		add[p] = 0; 
		for(int i = L[p];i <= R[p];i++) {
			if(a[i] < L[p]) b[i] = a[i];
			else b[i] = b[a[i]];
		}
		return;
	}
	for(int i = p + 1;i <= q-1;i++) {
		++cnt[i];
		add[i] = min(add[i]+x,100005);
		if(cnt[i] <= (int)sqrt(n)) {
			for(int j = L[i];j <= R[i];j++) {
				a[j] = max(a[j] - add[i],1);
			}
			add[i] = 0;
			for(int j = L[i];j <= R[i];j++) {
				if(a[j] < L[i]) b[j] = a[j];
				else b[j] = b[a[j]]; 
			} 
		}
	}
	for(int i = l;i <= R[p];i++) {
		a[i] = max(a[i]-x,1);
	}  
	for(int i = L[p];i <= R[p];i++) a[i] = max(a[i] - add[p],1);
	add[p] = 0;
	for(int i = L[p];i <= R[p];i++) {
		if(a[i] < L[p]) b[i] = a[i];
		else b[i] = b[a[i]];
	} 
	
	for(int i = L[q];i <= r;i++) {
		a[i] = max(a[i]-x,1);
	}
	for(int i = L[q];i <= R[q];i++) a[i] = max(a[i] - add[q],1);
	add[q] = 0;
	for(int i = L[q];i <= R[q];i++) {
		if(a[i] < L[q]) b[i] = a[i];
		else b[i] = b[a[i]];
	}
	return;
}

inline int query(int x,int y) {
	for(;;) {
		if(pos[x] != pos[y]) {
			if(pos[x] > pos[y]) swap(x,y);
			y = max(b[y] - add[pos[y]],1);
		}
		else {
			if(max(b[x] - add[pos[x]],1) != max(b[y] - add[pos[y]],1)) {
				x =	max(b[x] - add[pos[x]],1);
				y = max(b[y] - add[pos[y]],1);
			}
			else break;
		}
	}
	while(x != y) {
		if(x > y) swap(x,y);
		y = max(a[y] - add[pos[y]],1);
	}
	return y;
}

int main () {
	n = read();q = read();
	k = sqrt(n);
	for(int i = 2;i <= n;i++) a[i] = read();
	for(int i = 1;i <= k;i++) {
		L[i] = (i-1) * k + 1;
		R[i] = i * k;
	}
	if(R[k] < n) k++,L[k] = R[k-1] + 1,R[k] = n;
//	for(int i = 1;i <= k;i++) cout<<L[i]<<" "<<R[i]<<endl; 
	for(int i = 1;i <= k;i++) {
		for(int j = L[i];j <= R[i];j++) {
			if(a[j] < L[i]) {
				b[j] = a[j];
			}
			else b[j] = b[a[j]];
			pos[j] = i; 
		}
	}
	while(q--) {
		int opt;
		opt = read();
		if(opt == 1) {
			int l,r,x;
			l = read();r = read();
			x = read();
			change(l,r,x);
		}
		if(opt == 2) {
			int u,v;
			u = read();v = read(); 
			printf("%d\n",query(u,v));
		}
	}
	return 0;
}