题目描述

我们有一个有向图$G_S$，包含$N$个顶点，顶点从$1$到$N$编号。它有$N-1$条边。第$i$条边（$1\leq i \leq N-1$）从顶点$p_i\ (1\leq p_i \leq i)$指向顶点$i+1$。

我们还有另一个有向图$G$，包含$N$个顶点，顶点从$1$到$N$编号。最初，$G$等于$G_S$。按照给定的顺序在$G$上进行$Q$次查询。查询有两种类型，如下所示。

• 1 u v：将一条从顶点$u$指向顶点$v$的边添加到$G$中。保证满足以下条件。
  • $u \neq v$。
  • 在$G_S$上，通过一些边可以从顶点$v$到达顶点$u$。
• 2 x：打印从顶点$x$通过一些边可以到达的顶点中最小的顶点编号（包括顶点$x$）。

约束条件

• $2\leq N \leq 2\times 10^5$
• $1\leq Q \leq 2\times 10^5$
• $1\leq p_i\leq i$
• 对于第一种格式的每个查询：
  • $1\leq u,v \leq N$。
  • $u \neq v$。
  • 在$G_S$上，通过一些边可以从顶点$v$到达顶点$u$。
• 对于第二种格式的每个查询，$1\leq x \leq N$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $p_1$ $p_2$ $\dots$ $p_{N-1}$ $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$

这里，$\mathrm{query}_i$表示第$i$个查询，可以是以下任一格式之一：

$1$ $u$ $v$ $2$ $x$

输出

打印$q$行，其中$q$是第二种格式的查询数量。第$i$行（$1\leq j \leq q$）应该包含第$j$个查询的答案，即第二种格式中的查询结果。

示例输入 1

5
1 2 3 3
5
2 4
1 4 2
2 4
1 5 1
2 4

示例输出 1

4
2
1

• 在第一个查询时，只有顶点$4$可以通过一些边从顶点$4$到达$G$中的其他顶点。
• 在第三个查询时，顶点$2$、$3$、$4$和$5$可以通过一些边从顶点$4$到达在$G$中的其他顶点。
• 在第五个查询时，顶点$1$、$2$、$3$、$4$和$5$可以通过一些边从顶点$4$到达在$G$中的其他顶点。

示例输入 2

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

示例输出 2

5
2
1
1
1