함수의 맛

문제

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

레프가 파는 함수에서 자연수 1, ..., N의 맛은 각각 $A_{1}, \dots, 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_{1}, A_{2}, \dots, 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^{9}$)

• 3 x : 자연수 x부터 먹기 시작했을 때 이 함수의 맛이 얼마인지 출력한다. (1 ≤ x ≤ N)

출력

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

제한

• 1 ≤ N, Q ≤ 200,000

• 1 ≤ $A_{i}$ ≤ $10^{9}$ (1 ≤ i ≤ N)

• 3번 쿼리가 하나 이상 존재한다.

3 5
1 1 2
2 4 8
3 3
2 1 1
3 3
1 3 1
3 3

14
13
9

10 16
9 1 2 8 7 5 10 3 8 4
3 1 6 14 7 9 12 2 12 11
3 6
2 4 11
3 9
2 9 3
1 2 4
3 8
3 2
2 4 7
1 4 6
3 4
2 5 1
1 5 10
1 3 8
2 1 5
3 3
3 9

77
24
20
20
46
8
11

출처

• 문제를 만든 사람: TAMREF