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 $

서브태스크

힌트