[Contest #9]【XR-3】系统设计

内存限制：256 MB 时间限制：2500 ms

小 X 需要你设计一个系统。

这个系统首先需要输入一棵 $n$ 个点的有根树和一个长度为 $m$ 的序列 $a$，接下来需要实现 $q$ 个操作。

操作分两种：

1 x l r表示设定起点为有根树的节点 $x$，接下来依次遍历 $l \sim r$。当遍历到 $i$ 时，从当前节点走向它的编号第 $a_i$ 小的儿子。如果某一时刻当前节点的儿子个数小于 $a_i$，或者已经遍历完 $l \sim r$，则在这个点停住，并输出这个点的编号，同时停止遍历。
2 t k表示将序列中第 $t$ 个数 $a_t$ 修改为 $k$。

第一行 $3$ 个正整数 $n,m,q$，分别表示树的点数、序列的长度和操作个数。

第二行 $n$ 个整数 $f_{1 \dots n}$，其中 $f_i$ 表示点 $i$ 在树中的父亲节点编号，特别地，设根节点为 $rt$，则 $f_{rt} = 0$。

第三行 $m$ 个正整数 $a_{1 \dots m}$，表示序列 $a$。

接下来 $q$ 行，每行描述一个操作。

数据范围：

对于每个操作 $1$，一行一个正整数，表示答案。

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

本题读入、输出量较大，请使用读入、输出优化。

【样例说明】

第一个操作为1 1 1 3，即 $1 \rightarrow 2 \rightarrow 4$，因此答案为 $4$。

第九个操作后，序列变为2 1 2 1 2 1。

第十个操作为1 1 1 5，即 $1 \rightarrow 5 \rightarrow 6$，因此答案为 $6$。

C1362 [Contest #9]【XR-3】系统设计