Migrated from Lutece 2742 斐波拉契兔

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

总所周知，斐波拉契数列又可以称为兔子数列。

一天，兔子们想要搬进一个新的洞穴，但是由于兔子太多了，所以得重新开发洞穴使得兔子们都能入住。

洞穴的初始形态为一棵有着 $n$ 个节点的树，由于现在兔子现在都在外面，所以最初整个洞穴都是空的。

接下来会进行 $m$ 个操作使得来让兔子行动，操作的种类为 $3$ 种。

• $\texttt{1 x}$：在给定的节点 $x$ 处进入一只兔子。注意一个点上可以有多只兔子。

• $\texttt{2 x}$：发出一道号令，使得之前已经进入洞穴的兔子重新挖掘出一个点数为 $x$ 的菊花来得到更多的洞穴，注意 此处之前已经挖过洞穴的兔子仍然会进行操作，新挖出来的菊花所代表的洞穴会按照之前兔子进入的顺序进行标号，对于每一朵菊花，花心洞穴的编号将会排在花瓣洞穴的前面。 例如，当前有 $cnt$ 个节点时，第 $i$ 个放置兔子的节点挖出的菊花的花心洞穴编号为 $cnt+x \times ( i - 1 ) +1$，而花瓣洞穴的编号为 $[cnt + x \times ( i - 1 ) + 2, cnt + x × i]$。

• $\texttt{3 x y}$：表示一次查询，询问 $x$ 号洞穴和 $y$ 号洞穴的 $lca$。

Input

输入共 $m + 2$ 行。 第一行 $2$ 个数 $n$，$m$，表示初始点数和操作数。 接下来一行 $n-1$ 个数 $fa_2, fa_3...fa_n$，表示每个点的父亲。保证任意 $i\in [2,n] ,fa_i\le i$ 。 接下来 $m$ 行数表示操作。输入格式为 $opt_i, x_i$，特别的，如果 $opt_i = 3$ ，则格式为 $opt_i, x_i, y_i$。两整数之间有一空格隔开。

Output

对于每次询问，输出答案。

Samples

5 5
1 1 2 2
3 1 2
1 1
1 3
2 4
3 11 7

1
1

Constraints

$n \le 5 \times 10^5 , m \le 5 \times 10^5$

对于任意 $opt_i = 2, x_i \in [2, 10^6]$

对于任意$opt_i = 3 , x , y$ 均在 long long 范围内

题目保证数据均合法

Note

为了更为形象的解释操作 $2$ ,下面是样例的解释图。

Resources

2022 UESTC ICPC Training for Data Structures