【XR-3】系统设计

小 X 需要你设计一个系统。 这个系统首先需要输入一棵 $n$ 个点的有根树和一个长度为 $m$ 的序列 $a$，接下来需要实现 $q$ 个操作。 操作分两种： 1. `1 x l r` 表示设定起点为有根树的节点 $x$，接下来依次遍历 $l \sim r$。当遍历到 $i$ 时，从当前节点走向它的编号第 $a_i$ 小的儿子。如果某一时刻当前节点的儿子个数小于 $a_i$，或者已经遍历完 $l \sim r$，则在这个点停住，并输出这个点的编号，同时停止遍历。 2. `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 \le n,m,q \le 5 \times 10 ^ 5$。 - $1 \le a_i \le n$。 - 对于操作 $1$，保证 $1 \le x \le n$，$1 \le l \le r \le m$。 - 对于操作 $2$，保证 $1 \le t \le m$，$1 \le k \le n$。

对于每个操作 $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

4
5
6
4
3
3
4
6

本题读入、输出量较大，请使用[读入、输出优化](https://oi-wiki.org/misc/io/)。 【样例说明】 第一个操作为 `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$。