wwx 的兔子打洞计划

题目描述

wwx 最近养了很多兔子，这天，她想让她的兔子们搬进一个新的洞穴，但是由于兔子太多了，所以得重新开发洞穴使得兔子们都能入住。

wwx 挖了一个初始形态的洞穴，是一棵有着 $n$ 个节点的树，一开始兔子们都在外面，所以最初整个洞穴都是空的。

接下来 wwx 会安排她的兔子们进行 $m$ 次操作，操作的种类有 $3$ 种。

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

2 x：发出一道号令，让已经进入洞穴的所有兔子从它在的节点出发，挖掘出一个共计 $x$ 个节点的的菊花洞穴，注意 此处之前已经挖过洞穴的兔子仍然会进行操作，并且挖完洞以后的兔子们都会回到原本的洞穴，新挖出来的菊花洞穴会按照之前兔子进入洞穴的顺序进行标号，对于每一只兔子挖的菊花洞穴，花心洞穴的编号将会排在花瓣洞穴的前面。 例如，当前有 $cnt$ 个洞穴中，第 $i$ 只进入兔子所处节点为 $A$ ,它挖出的菊花洞穴的花心编号为 $cnt+x \times ( i - 1 ) +1$，而花瓣洞穴的编号为 $[cnt + x \times ( i - 1 ) + 2, cnt + x × i]$，其中节点 $A$ 会和花心洞穴相连，所有的花瓣洞穴会和花心洞穴相连

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

输出格式

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

数据范围

本题一共有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 范围内

题目保证数据均合法

样例输入

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

样例输出

1
1