18374번 - 함수의 맛

인덱스 트리 상인 탐레프는 인덱스국의 멸망 이후로 아무도 인덱스 트리를 사주지 않자, 인기 간식인 함수 f : {1, ..., N} → {1, ..., N}을 만들어 파는 중이다.

레프가 파는 함수에서 자연수 1, ..., N의 맛은 각각 A₁, ...,A_N으로 알려져 있는데, 이 값은 재료의 품질에 따라서 매일 바뀐다. 함수를 먹을 때는 마음에 드는 자연수 x를 정해서 x, f(x), f(f(x)), ...를 차례로 먹으면 되는데, 같은 수를 여러 번 먹지는 않는다. 즉, i = 1, ..., N에 대해 i = f^k(x)인 k ≥ 0이 존재한다면 자연수 i를 먹는다. 이렇게 먹었을 때 느끼는 함수의 맛은 먹은 모든 자연수의 맛을 합한 값이다.

레프는 숙련된 주방장이 아니기 때문에, 종종 f의 구조를 바꿔버리기도 한다. 대신 레프는 손님의 "x부터 먹기 시작하면 이 함수의 맛은 얼마인가요?"라는 질문에 빠르게 답할 수 있는 기계를 만들기로 했다.

1번째 줄에는 함수의 정의역과 공역의 크기를 나타내는 자연수 N과 쿼리의 수 Q가 공백으로 구분되어 주어진다.
2번째 줄에는 함숫값 f(1), ..., f(N)이 공백으로 구분되어 주어진다.
3번째 줄에는 각 자연수의 맛 A₁, A₂, ..., A_N이 공백으로 구분되어 주어진다.
4번째 줄부터 Q줄에 걸쳐 레프가 구현해야 하는 쿼리가 주어진다.

• 1 i j : f(i)를 j로 바꾼다. (1 ≤ i, j ≤ N)
• 2 i x : 자연수 i의 맛 A_i를 x로 바꾼다. (1 ≤ i ≤ N, 1 ≤ x ≤ 10⁹)
• 3 x : 자연수 x부터 먹기 시작했을 때 이 함수의 맛이 얼마인지 출력한다. (1 ≤ x ≤ N)

3번 쿼리에 대한 답을 순서대로 한 줄에 하나씩 출력한다.

• 1 ≤ N, Q ≤ 200,000
• 1 ≤ A_i ≤ 10⁹ (1 ≤ i ≤ N)
• 3번 쿼리가 하나 이상 존재한다.