系统设计

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

小 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$。

输入格式

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

第二行包含 $n$ 个整数 $f_1,f_2,\ldots,f_n$，其中 $f_i$ 表示节点 $i$ 的父亲编号。特别地，设根节点为 $rt$，则 $f_{rt}=0$。

第三行包含 $m$ 个正整数 $a_1,a_2,\ldots,a_m$，表示序列 $a$。

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

输出格式

对于每个操作 $1$，输出一行一个正整数，表示本次遍历最终停留的节点编号。

样例输入 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

4
5
6
4
3
3
4
6

数据范围

• $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 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$。