题目描述

小 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

提示

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

【样例说明】

第一个操作为 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$。