Composite Function and Queries 2

Time limit2sMemory limit512 MB

Summary

Maintain a function f on {1..N} under updates to f(1) and queries asking for the m-fold iterate f^m(x).

Level: Hard8 of 10
Topics: Graph, Binary search, Prefix sum, Math
Solved: No attempts yet

Problem

You are given the values $f(1), f(2), \cdots, f(N)$ of a function $f : \{1, 2, \cdots, N\} \to \{1, 2, \cdots, N\}$ . Write a program that handles the following queries.

1 x: change the value of $f(1)$ to $x$ .
2 m x: print the value of $f^m(x)$ .

Here $f^m$ is the function obtained by composing $f$ with itself $m$ times: $f^1(x) = f(x)$ , and for every positive integer $m \ge 2$ , $f^m(x) = (f \circ f^{m-1})(x) = f(f^{m-1}(x))$ .

Input

The first line gives the positive integer $N$ .

The second line gives the initial values $f(1), f(2), \cdots, f(N)$ in order.

The third line gives the number of queries $Q$ .

Each of the next $Q$ lines contains one query.

Output

Print the result of each type 2 query, one per line.

Constraints

$1 \le N \le 200\,000$
$1 \le f(i) \le N$
$1 \le Q \le 500\,000$
For a type 1 query, $1 \le x \le N$
For a type 2 query, $1 \le m \le 10^9$ and $1 \le x \le N$

Examples1

Example 1
Input
```
4
2 3 4 1
3
2 3 1
1 3
2 3 1
```
Expected output
```
4
1
```