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 <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

#include <cmath>
#include <queue>
#include <stack>

#include <unordered_set>
#include <unordered_map>
#include <array>

using namespace std;
#define LL long long

// #ifndef DEBUG_FLAG
// #define DEBUG_FLAG
// #endif

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x) {
    if (x < 0) {
		putchar('-'); x = -x;
	}
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writeln(int x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}

inline LL readll() {
    LL x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void writell(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writellln(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}

int blockS, blockN;
int n, q;

vector<LL> updN;
vector<LL> a;
vector<LL> f;

vector<LL> af, aa;
vector<bool> flag;

int getBlock(int x) {
    return x / blockS;
}

LL getF(int u) {
    return (u == 0) ? -1 : max(a[u] - updN[u / blockS], (LL)(0));
}

// void updateCompleteBlock(int b, int x) {
//     // we want to maintain: a[i], f[i]
//     // for a[i]: always update by updN[b] += x
//     // for f[i]: stop updating if updN[b] >= blockS
//     if (flag[b]) {
//         updN[b] += x; // times for -1 operation
//         return ;
//     }
//     flag[b] = true;
//     for (int i = blockS * b; i < min(blockS * (b + 1), n); ++i) {
//         // update f[i]
//         // also we need a fenwick tree to keep the ancestors
//         // real a[i]: a[i] - updN[b]
//         // new real a[i]: a[i] - updN[b] - 1
//         // if out: then f[i] = i
//         // otherwise, f[i] = f[a[i]]
//         a[i] = max(a[i] - x, 0);
//         if (a[i] < blockS * b) {
//             f[i] = i;
//         } else {
//             f[i] = f[a[i]]; flag[b] = false;
//         }
//     }
// }

void updateCompleteBlock(int b, int x) {
    // we want to maintain: a[i], f[i]
    // for a[i]: always update by updN[b] += x
    // for f[i]: stop updating if updN[b] >= blockS
    if (updN[b] > blockS) {
        updN[b] += x; // times for -1 operation
        return ;
    }
    updN[b] += x;
    for (int i = blockS * b; i < min(blockS * (b + 1), n); ++i) {
        // update f[i]
        // also we need a fenwick tree to keep the ancestors
        // real a[i]: a[i] - updN[b]
        // new real a[i]: a[i] - updN[b] - 1
        // if out: then f[i] = i
        // otherwise, f[i] = f[a[i]]
        if (getF(i) < blockS * b) {
            f[i] = i;
        } else {
            f[i] = f[getF(i)];
        }
    }
}

void updatePartial(int b, int l, int r, int x) {
    #ifdef DEBUG_FLAG
        printf("updatePartial(b = %d, l = %d, r = %d, x = %d)\n", b, l, r, x);
    #endif
    for (int i = l; i < min((b + 1) * blockS, n); ++i) {
        if (i <= r) {
            a[i] -= x; 
        }
        if (getF(i) < blockS * b) {
            f[i] = i;
        } else {
            f[i] = f[getF(i)];
        }
    }
}

void update(int l, int r, int x) {
    // update [l, r]
    // first find blocks
    int bl = getBlock(l), br = getBlock(r);
    if (bl == br) {
        updatePartial(bl, l, r, x);
        return ;
    }
    // if (l % blockS == 0) {
    //     updateCompleteBlock(bl, x);
    // } else {
    updatePartial(bl, l, min((bl + 1) * blockS - 1, n - 1), x);
    // }
    for (int b = bl + 1; b < br; ++b) {
        updateCompleteBlock(b, x);
    }
    // if (r % blockS == blockS - 1) {
    //     updateCompleteBlock(br, x);
    // } else {
    updatePartial(br, br * blockS, r, x);
    // }

    #ifdef DEBUG_FLAG

    for (int i = l; i <= r; ++i) {
        aa[i] = max(aa[i] - x, 0);
    }
    for (int i = 1; i < n; ++i) {
        if (getBlock(aa[i]) != getBlock(i)) {
            af[i] = i;
        } else {
            af[i] = af[aa[i]];
        }
    }

    #endif
}

// vector<bool> vis;
// vector<int> vs;

// void clv() {
//     for (int u: vs) {
//         vis[u] = false;
//     }
//     // vis.clear();
//     vs.clear();
// }

int query(int u, int v) {
    // note that for u: the real a[u] is max(a[u] - updN[u / blockS], 0)
    // first tune u and v to the same block
    int fu = getF(f[u]), fv = getF(f[v]);
    while (fu != fv) {
        #ifdef DEBUG_FLAG
        printf("upping blocks: u = %d, v = %d\n", u, v);
        printf("aa[%d] = %d, aa[%d] = %d\n", u, aa[u], v, aa[v]);
        #endif
        if (getBlock(u) > getBlock(v)) {
            u = fu; fu = getF(f[u]);
        } else {
            v = fv; fv = getF(f[v]);
        }
    }
    // if (getBlock(u) > getBlock(v)) {
    //     swap(u, v);
    // }
    // printf("query(u = %d, v = %d)\n", u, v);
    // while (getBlock(v) > getBlock(u)) {
    //     printf("upping blocks: u = %d, v = %d\n", u, v);
    //     v = getF(f[v]);
    // }

    // while (u != fu) {
    //     #ifdef DEBUG_FLAG
    //     cout << "upping u = " << u << endl;
    //     #endif
    //     vis[u] = true; vs.push_back(u);
    //     u = getF(u);
    // }
    // while (v != fu) {
    //     #ifdef DEBUG_FLAG
    //     cout << "upping v = " << v << endl;
    //     #endif
    //     if (vis[v]) {
    //         clv(); return v;
    //     }
    //     v = getF(v);
    // }
    // clv();
    // return fu;
    while (u != v) {
        #ifdef DEBUG_FLAG
            printf("working in same block: u = %d, v = %d\n", u, v);
            printf("aa[u = %d] = %d, aa[v = %d] = %d\n", u, aa[u], v, aa[v]);
            printf("a[u = %d] = %d, a[v = %d] = %d\n", u, a[u], v, a[v]);
            printf("updN[b = %d] = %d\n", u / blockS, updN[u / blockS]);
            printf("getF(v = %d) = %d\n", v, getF(v));
        #endif
        if (u > v) {
            swap(u, v); continue;
        } else {
            v = getF(v);
        }
    }

    return u;

    // int fu = getF(u), fv = getF(v);
    // while (fu != fv) {
    //     if (getBlock(fu) < getBlock(fv)) {
    //         // then fv go up
    //         v = fv; fv = getF(f[v]);
    //     } else {
    //         u = fu; fu = getF(f[u]);
    //     }
    // }
    // if (u == v) {
    //     return u;
    // } else {
    //     return fu;
    // }
}

void compare() {
    cout << "comparing" << endl;
    for (int i = 0; i < n; ++i) {
        // cout << getF(i) << ' ' << aa[i] << endl;
        if (getF(i) != aa[i]) {
            printf("diff at a[%d]: get %lld, expect %lld\n", i, getF(i), aa[i]);
        }
        if (f[i] != af[i]) {
            printf("diff at f[%d]: get %lld, expect %lld\n", i, f[i], af[i]);
        }
    }
}
void solve() {
    n = read(); q = read();

    blockS = int(sqrt(n));
    blockN = (n + blockS - 1) / blockS;
    updN = vector<LL>(blockN, 0);
    // flag = vector<bool>(blockN, false);

    a = vector<LL>(n);
    for (int i = 1; i < n; ++i) {
        a[i] = read() - 1;
    }
    a[0] = -1;
    f = vector<LL>(n, -1);
    f[0] = 0;
    for (int i = 1; i < n; ++i) {
        if (getBlock(a[i]) != getBlock(i)) {
            f[i] = i;
        } else {
            f[i] = f[a[i]];
        }
    }

    // vis = vector<bool>(n, false);

    // cout << "here" << endl;

    #ifdef DEBUG_FLAG

    af = f; aa = a;
    #endif

    int opt, u, v;
    int l, r, x;

    for (int i = 0; i < q; ++i) {
        opt = read();
        if (opt == 1) {
            l = read() - 1; r = read() - 1; x = read();
            update(l, r, x);
        } else {
            u = read() - 1; v = read() - 1;
            writeln(query(u, v) + 1);
        }

        #ifdef DEBUG_FLAG
            compare();
        #endif
    }
    #ifdef DEBUG_FLAG
    cout << "block size = " << blockS << endl;
    cout << "block n = " << blockN << endl;
    #endif

}

int main() {
	// std::ios::sync_with_stdio(false);
    // std::cin.tie(0);

    #ifdef DEBUG_FLAG

    cout << "debug mode!" << endl;

    #endif
	int t = 1;
	for (int i = 0; i < t; ++i) {
		solve();
	}
	return 0;
}