Problem Description

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$.

Input Format

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$.

Output Format

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

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

Hint

The input and output size of this problem is large. Please use fast input/output.

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