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>
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Rep(i,a,b) for (int i=b;i>=a;i--)
#define log(x) (31-__builtin_clz(x))
#define TASK "H" 
#define int long long
using namespace std;


const int N=100007;
int block[N],fa[N];
int anc[N];
int n,q;
int max (int x,int y){
    return x>y ? x:y;
}
struct __blocks{
    int st,ed;
    // int flag = 0;
    long long lazy = 0;
    void update(int x){
        lazy += x;
    }
    // void check(){
    //     flag = 1;
    //     For(i,st,ed){
    //         if (anc[i] != i){
    //             flag = 0;
    //             return;
    //         }
    //     }
    // }
}bl[N];
int block_size;


int getfa(int x){
    return max(fa[x] - bl[block[x]].lazy , 1LL);
}
void check(int i){
    if (block[i]==1) anc[i]=1;
    else {
        if (block[i] == block[getfa(i)]) anc[i] = anc[getfa(i)];
        else anc[i] = i;
    }
}
void updfa(int i,int x){
    fa[i] = max(1,fa[i]-x);
    check(i);
}

void update(int l,int r,int x){
    // cout << l << ' ' << r  << ' ' << x << endl;
    if (block[l] == block[r]){
        // cout <<'Y' << endl;
        For(i,l,r){
            updfa(i,x);
        }
        For(i,bl[block[l]].st,bl[block[l]].ed) check(i);
        return;
    }
    For(i,l,bl[block[l]].ed) updfa(i,x);
    For(i,bl[block[l]].st,bl[block[l]].ed) check(i);
    // bl[block[l]].check();
    For(i,bl[block[r]].st,r) updfa(i,x);
    For(i,bl[block[r]].st,bl[block[r]].ed) check(i);
    // bl[block[r]].check();
    For(i,block[l]+1,block[r]-1){
        // if (bl[i].flag) bl[i].update(x);
        // else{ 
        //     For(now,bl[i].st,bl[i].ed) updfa(now,x);
        //     bl[i].check();
        // }
        bl[i].lazy += x;
        // cout << "U " << i << "  Lazy = " << bl[i].lazy << endl;
        if (bl[i].lazy - x <= block_size){
            // cout << "C " << i << ' ' << bl[i].st << ' ' << bl[i].ed << endl;
            For(now,bl[i].st,bl[i].ed){
                check(now);
            }
        }
    }

}

void query(int x,int y){
    // while (anc[x] != anc[y]){
    //     if (anc[x] < anc[y]) swap(x,y);
    //     x = getfa(anc[x]);
    //     // cout << "Block " << x << ' ' << y << endl;
    // }
    // while (x != y){
    //     if (x < y) swap(x,y);
    //     x = getfa(x);
    //     // cout << "Getfa " <<  x << ' ' << getfa(x) << ' ' << y << ' ' << getfa(y) << endl;
    // }
    // cout << x << endl;
    // return;

    // cout << "Query : " << x << ' ' << y << endl;

    while (anc[x] != anc[y]){
        if (anc[x] > anc[y]) swap(x,y);
        y = getfa(anc[y]);
        // cout << x << ' ' << y << endl;
        // cout << anc[x] << ' ' << anc[y] << endl << endl; 
    }
    if (x == y){
        cout << x << endl;
        return;
    }
    while (getfa(x) != getfa(y)){
        if (getfa(x) < getfa(y)) swap(x,y);
        x = getfa(x);
    }
    if (x==y) cout << x << endl;
    else cout << getfa(x) << endl;

}

signed main(){

    #ifndef ONLINE_JUDGE
    freopen(TASK".in","r",stdin);
    freopen(TASK".out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> q;
    block_size = (int) sqrt(n);
    fa[1]=0;
    For(i,1,n){
        block[i] = ((i-1) / block_size) + 1;
        if (i>1) cin >> fa[i];
        check(i);
    }
    For(i,1,block[n]){
        bl[i].st = (i-1) * block_size + 1;
        bl[i].ed = min(i * block_size , n);
        // bl[i].check();
    }
    // cout << block [112] << ' ' << block[118] << endl;

    int flag=0;

    For(test,1,q){
        // For(i,1,n) cout << fa[i] << ' '; cout << endl;
        // For(i,1,n) cout << anc[i] << ' '; cout << endl;
        // cout << fa[11] << ' ' << anc[11] << endl;
        // cout << "ANC 118 = " << anc[118] << "  Fat 118 = " << getfa(118) <<endl;
        int opt;
        cin >> opt;
        
        if (opt == 1){
            int l,r,x;
            cin >> l >> r >> x;
            update(l,r,x);
        }
        else {
            int l,r;
            cin >> l >> r;
            flag ++;
            // if (flag != 307) continue;
            query(l,r);
        }
    }

}