题目描述

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

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

洞穴的初始形态为一棵有着 $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$。

输入

输入共 $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$。两整数之间有一空格隔开。

输出

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

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

1
1

见附件中的sample.in

见附件中的sample.out

样例说明

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

可以看出，$2$ 次询问的 $LCA$ 均为 $1$ 。

数据范围

本题一共有16组数据。

test 1 (1个测试点共 7 分 ) ：$n\le 10^5,\forall i \in [1,m],opt_i=3$。

test 2~4 (3个测试点共 21 分) ：保证最终的点数不超过 $10^7$ 个。

test 5~7 (3个测试点共 21 分) : 保证所有的 $2$ 操作均在 $1$ 操作之后

test 8~10 (3个测试点共 21 分): 保证所有的 $3$ 操作均在所有操作之后

test 11~16(6个测试点共 30 分): 没有特殊限制。

对于所有数据，$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 范围内

题目保证数据均合法

附件下载

T4sample