P5537 [XR-3] System Design

Little X needs you to design a system. This system first needs to read a rooted tree with $n$ nodes and a sequence $a$ of length $m$, and then process $q$ operations. There are two types of operations: 1. `1 x l r` means: set the starting point as node $x$ in the rooted tree, then traverse $l \sim r$ in order. When traversing to $i$, move from the current node to its $a_i$-th smallest child (by node index). If at some moment the current node has fewer than $a_i$ children, or you have already finished traversing $l \sim r$, then stop at this node, output its index, and stop traversing. 2. `2 t k` means: modify the $t$-th number in the sequence, changing $a_t$ to $k$.

The first line contains $3$ positive integers $n, m, q$, representing the number of nodes in the tree, the length of the sequence, and the number of operations. The second line contains $n$ integers $f_{1 \dots n}$, where $f_i$ is the index of the parent of node $i$ in the tree. In particular, let the root be $rt$, then $f_{rt} = 0$. The third line contains $m$ positive integers $a_{1 \dots m}$, representing the sequence $a$. Then follow $q$ lines, each describing one operation. **Constraints:** - $1 \le n, m, q \le 5 \times 10 ^ 5$. - $1 \le a_i \le n$. - For operation type $1$, it is guaranteed that $1 \le x \le n$, $1 \le l \le r \le m$. - For operation type $2$, it is guaranteed that $1 \le t \le m$, $1 \le k \le n$.

For each operation of type $1$, output one positive integer per line, representing the answer.

The input and output size of this problem is large. Please use [fast input/output](https://oi-wiki.org/misc/io/). **Sample Explanation** The first operation is `1 1 1 3`, that is, $1 \rightarrow 2 \rightarrow 4$, so the answer is $4$. After the ninth operation, the sequence becomes `2 1 2 1 2 1`. The tenth operation is `1 1 1 5`, that is, $1 \rightarrow 5 \rightarrow 6$, so the answer is $6$. Translated by ChatGPT 5