시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 (추가 시간 없음) 1024 MB 77 8 8 32.000%

문제

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

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

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

입력

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

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

출력

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

제한

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

예제 입력 1

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

예제 출력 1

14
13
9

예제 입력 2

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

예제 출력 2

77
24
20
20
46
8
11

출처

Contest > IDTcup > 제 2회 IDTcup B번

  • 문제를 만든 사람: TAMREF