합성함수와 쿼리 2

함수 $f : \{1, 2, \cdots, N\} \to \{1, 2, \cdots, N\}$의 각 함숫값 $f(1), f(2), \cdots, f(N)$이 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 x : $f(1)$의 값을 $x$로 변경한다.
• 2 m x : $f^m(x)$의 값을 출력한다.

여기서 $f^m$은 $f$를 $m$번 합성한 함수이다. 즉 $f^1(x) = f(x)$이고, $m \ge 2$인 모든 자연수 $m$에 대해 $f^m(x) = (f \circ f^{m-1})(x) = f(f^{m-1}(x))$를 만족한다.

첫째 줄에 자연수 $N$이 주어진다.

둘째 줄에는 초기 상태의 $f(1), f(2), \cdots, f(N)$이 차례대로 주어진다.

셋째 줄에는 쿼리의 개수 $Q$가 주어진다.

넷째 줄부터 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

2번 쿼리의 결과를 한 줄에 하나씩 출력한다.

• $1 \le N \le 200\,000$
• $1 \le f(i) \le N$
• $1 \le Q \le 500\,000$
• 1번 쿼리의 경우 $1 \le x \le N$
• 2번 쿼리의 경우 $1 \le m \le 10^9$, $1 \le x \le N$