No legend — Eolymp

Input

The first line contains two integers $n$ and $q (2 \leq n, q \leq 1 0^{5})$ q\:(2 \le n, q \le 10^5) — the number of vertices and the number of queries, respectively.

The second line contains $n - 1$ n - 1 integers $a_{2}, a_{3}, ..., a_{n} (1 \leq a_{i} < i)$ a_2, a_3, ..., a_n\:(1 \le a_i < i), where $a_{i}$ a_i is the parent of the node $i$ .

The following $q$ rows contain queries. For each query, the first integer of the string is $t (t = 1$ t\:(t = 1 or $2)$ query type.

If $t = 1$ t = 1, then this is a query of the first type. Then three integers will follow: $l, r, x (2 \leq l \leq r \leq n, 1 \leq x \leq 1 0^{5})$ l, r, x\:(2 \le l \le r \le n, 1 \le x \le 10^5), which means that you need to replace $a_{i}$ a_i with $ma x (a_{i} - x, 1)$ max(a_i - x, 1) for all $i$ with $l \leq i \leq r$ l \le i \le r.

If $t = 2$ t = 2, then this is a query of the second type. Then two integers will follow: $u$ and $v (1 \leq u, v \leq n)$ v\:(1 \le u, v \le n), and you should find the $L C A$ of $u$ and $v$ .

It is guaranteed that there is at least one query of the second type.

Output

For each query of the second type, print the answer in a new line.

Examples

Example 1

Loading