함수의 맛

인덱스 트리 상인 탐레프는 인덱스국이 멸망한 뒤 아무도 인덱스 트리를 사 가지 않자, 인기 간식인 함수 $f: \{1, \ldots, N\} \to \{1, \ldots, N\}$을 만들어 판다.

레프가 파는 함수에서 자연수 $1, \ldots, N$의 맛은 각각 $A_1, \ldots, A_N$으로 알려져 있다. 이 값은 재료의 품질에 따라 매일 바뀐다. 함수를 먹을 때는 마음에 드는 자연수 $x$를 골라 $x, f(x), f(f(x)), \ldots$를 차례로 먹는다. 단, 같은 수는 두 번 먹지 않는다. 즉, 각 $i = 1, \ldots, N$에 대해 $i = f^k(x)$인 $k \ge 0$이 존재하면 자연수 $i$를 먹는다. 이렇게 먹은 모든 자연수의 맛을 합한 값이 함수의 맛이다.

레프는 숙련된 주방장이 아니라서 $f$의 구조를 종종 바꾼다. 대신 손님이 '$x$부터 먹기 시작하면 이 함수의 맛은 얼마인가요?'라고 물으면 빠르게 답할 수 있는 기계를 만들기로 했다.

첫째 줄에 함수의 정의역과 공역의 크기 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. 둘째 줄에는 $f(1), \ldots, f(N)$이 공백으로 구분되어 주어진다. 셋째 줄에는 $A_1, \ldots, A_N$이 공백으로 구분되어 주어진다. 넷째 줄부터 $Q$줄에 걸쳐 다음 쿼리가 주어진다.

• 1 i j: $f(i)$를 $j$로 바꾼다. ($1 \le i, j \le N$)
• 2 i x: 자연수 $i$의 맛 $A_i$를 $x$로 바꾼다. ($1 \le i \le N$, $1 \le x \le 10^9$)
• 3 x: 자연수 $x$부터 먹기 시작했을 때 이 함수의 맛을 출력한다. ($1 \le x \le N$)

3번 쿼리마다 답을 한 줄에 하나씩 출력한다.

• $1 \le N, Q \le 200{,}000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• 3번 쿼리가 하나 이상 주어진다.