23894번 - 합성함수와 쿼리 2 서브태스크

함수 $f : \{1, 2, \cdots, N\} → \{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 $