Rooted Tree Traversal System

You are given a rooted tree with \(n\) nodes and a sequence \(a\) of length \(m\). The tree is specified by the parent of every node (except for the root). The children of each node are kept sorted in increasing order. You are also given \(q\) operations to perform on the tree and the sequence.

There are two types of operations:

1. 1 x l r: Starting from node \(x\), traverse the sequence from index \(l\) to \(r\) (1-indexed). When processing element \(a_i\) in the sequence, if the current node has at least \(a_i\) children, move to the \(a_i\)-th smallest child. Otherwise (i.e. if the current node has fewer than \(a_i\) children or if the traversal has finished), stop the traversal and output the current node's number.
2. 2 t k: Update the sequence by setting \(a_t = k\).

Note: All indices in the sequence are 1-indexed.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\).

The second line contains \(n-1\) integers, where the \(i\)-th integer (for \(i = 2, 3, \ldots, n\)) denotes the parent of node \(i\) in the rooted tree. Node 1 is the root of the tree.

The third line contains \(m\) integers representing the sequence \(a = [a_1, a_2, \ldots, a_m]\).

Each of the following \(q\) lines contains an operation in one of the following two formats:

• 1 x l r
• 2 t k

outputFormat

For each operation of type 1, print a single line containing the number of the node where the traversal stops.

sample

5 5 3
1 1 2 2
1 2 1 2 1
1 1 1 3
2 2 1
1 1 1 3

5
4