CF1491H.Yuezheng Ling and Dynamic Tree

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 \leq a_i \lt i$ for $2 \le i \le 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 \le l \le r \le n$, $1 \le x \le 10^5$). You need to replace $a_i$ with $\max(a_i-x,1)$ for all $i$ with $l \leq i \leq r$.
2. She'll give you two integers $u$, $v$ ($1 \le u, v \le n$). You need to find the LCA of nodes $u$ and $v$ (their lowest common ancestor).

岳正灵送给洛天依一棵有 $n$ 个节点的树，根节点为 $1$。

洛天依会告诉你第 $i$ 个节点的父节点是 $a_i$（其中对 $2 \le i \le n$，满足 $1 \leq a_i < i$），并要求你执行 $q$ 次查询，查询分为两类：

1. 她会给出三个整数 $l$、$r$ 和 $x$（满足 $2 \le l \le r \le n$，$1 \le x \le 10^5$）。你需要对所有满足 $l \leq i \leq r$ 的 $i$，将 $a_i$ 替换为 $\max(a_i - x,\, 1)$。
2. 她会给出两个整数 $u$、$v$（满足 $1 \le u, v \le n$）。你需要求出节点 $u$ 和 $v$ 的 LCA（即它们的最近公共祖先）。

The first line contains two integers $n$ and $q$ ($2\leq n,q \leq 10^5$) — the number of nodes and the number of queries, respectively.

The second line contains $n-1$ integers $a_2, a_3,\dots, a_n$ ($1 \le a_i \lt 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 \le l \le r \le n$, $1 \le x \le 10^5$), meaning that you have to replace $a_i$ with $\max(a_i-x,1)$ for all $i$ with $l \leq i \leq r$.

If $t = 2$, this represents the query of the second type. Then, two integers will follow: $u$ and $v$ ($1 \le u, v \le 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.

第一行包含两个整数 $n$ 和 $q$（$2\leq n,q \leq 10^5$），分别表示节点数量和查询数量。

第二行包含 $n-1$ 个整数 $a_2, a_3,\dots, a_n$（$1 \le a_i \lt i$），其中 $a_i$ 表示节点 $i$ 的父节点。

接下来 $q$ 行为查询。每行查询以一个整数 $t$（$t = 1$ 或 $2$）开头，表示查询类型。

若 $t = 1$，表示第一类查询。随后将给出三个整数：$l$、$r$、$x$（$2 \le l \le r \le n$，$1 \le x \le 10^5$），表示对所有满足 $l \leq i \leq r$ 的 $i$，将 $a_i$ 替换为 $\max(a_i-x,1)$。

若 $t = 2$，表示第二类查询。随后将给出两个整数：$u$ 和 $v$（$1 \le u, v \le n$），要求计算 $u$ 与 $v$ 的最近公共祖先（LCA）。

保证至少存在一个第二类查询。

For each query of the second type output answer on a new line.

对于每个第二类查询，在新行中输出答案。

The tree in example is shown below.

After the query of the first type, the tree changes and is looking as shown below.

示例中的树如下所示。

执行第一类查询后，树发生变化，结果如下图所示。