圣诞节就要到了，小C想买一棵圣诞树。自然，请客请到破产的小C买不起圣诞树，所以，小C计划把过年用的许愿树改造成圣诞树。

许愿树是一棵 $n$ 个节点的二叉搜索树，$n$ 个节点的权值为 $1$ 到 $n$ 的排列。

我们定义一次单旋为：

假设 $x$ 是其父亲 $p$ 的左孩子。我们对它做下图操作，则称为一次单旋。

如果是右孩子，就做其轴对称操作。

圣诞树支持如下三个操作：

1. 点 $x$ 连续不断单旋向上，直至它成为点 $y$ 的儿子，保证 $y$ 是 $x$ 的祖先
2. 询问点 $x$ 的第 $k$ 级祖先，保证此时点 $x$ 的第 $k$ 级祖先存在
3. 询问整棵树先序遍历中的第 $k$ 个点，保证此时$1\le k \le n$。

许愿树不支持这些操作，现在小C希望你能帮助他加上这些功能。

输入格式

第一行一个正整数 $n$ 表示许愿树的节点数。

第二行 $n$ 个正整数，记第 $i$ 个整数 $f_i$ 表示权值为 $i$ 的节点的父亲。

如果 $f_i=0$，表示该节点是根。 你可以通过 $i$ 与 $f_i$ 的相对大小来确定该节点是其父亲的左孩子还是右孩子。 保证所形成树结构是一棵二叉搜索树。

第三行一个正整数 $m$ 表示操作次数。

接下来 $m$ 行，每行先输入一个整数 $opt$，保证 $1 \le opt \le 3$ 。

如果 $opt=1$ ，则之后还跟着两个正整数 $x,y$ ，表示将点 $x$ 连续不断单旋向上，直至它成为点 $y$ 的儿子。

如果 $opt=2$ ，则之后还跟着两个正整数 $x,k$ ，表示询问询问点 $x$ 的第 $k$ 级祖先。

如果 $opt=3$ ，表示询问整棵树先序遍历中的第 $k$ 个点。

输出格式

输出若干行，每行一个整数表示询问的答案。

10
2 3 5 3 9 8 6 5 0 9 
10
3 9
1 1 2
2 1 4
1 4 5
1 4 5
2 1 3
1 2 4
2 8 1
2 10 1
2 8 2

7
9
4
5
9
9

样例二至样例六

见样例数据下载。

限制与约定

本题采用捆绑测试，对于每个子任务，只有通过其中全部数据才可以获得分数。 对于全部数据，$1 \le n,m \le 100000$，$0 \le f_i \le n$

特殊性质 0：保证数据随机。

特殊性质 1：保证所有修改都在询问之前。

特殊性质 2：保证每次一操作中的点 $y$ 都是整棵树的根。

特殊性质 3：保证没有三操作

特殊性质 4：保证所有二操作中$k = 1$。

特殊性质 5：保证没有二操作

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$

下载

样例数据下载