문제아

경기과학고등학교의 SRC(Science Research City) $8$층에는 이승원, 황젠슨, 김명준 주니어 등 전설적인 인재들을 배출한 병설유치원인 경곽유치원이 있다. 경곽유치원 햇살반에는 $N$명의 어린이와 $K$개의 모둠이 있다. 모든 어린이는 각각 정확히 하나의 모둠에 속한다.

유아교육과가 아닌 공대를 졸업한 김명준 선생님은 어린이들에게 점수를 매긴다. 햇살반의 모든 활동은 모둠 활동이기 때문에 김명준 선생님은 하나의 모둠에 속한 모든 어린이들의 점수를 함께 바꾼다.

경곽유치원 최대 문제아인 아기새반의 윤찬이는 햇살반의 어린이 한 명의 모둠을 바꾸는 아주 나쁜 행동을 하기 시작했다! 당신은 문제아가 아닌 스스로 어린이이기 때문에 김명준 선생님과 윤찬이의 행동 중에 어떤 어린이의 현재 점수를 알아내고자 한다.

모든 행동은 다음과 같은 쿼리로 입력된다. 초기 햇살반 어린이들의 점수는 모두 $0$이다.

• 1 i c : 문제아 윤찬이가 $i$번째 어린이를 $c$번 모둠으로 옮긴다. 만약 $i$번째 어린이가 원래 $c$번 모둠에 속해 있었다면 아무 일도 일어나지 않는다.
• 2 c x : 김명준 선생님이 $c$번 모둠인 모든 어린이의 점수에 $x$를 더한다.
• 3 i : $i$번째 어린이의 현재 점수를 출력한다.

첫 번째 줄에 햇살반 어린이의 인원수 $N$과 모둠의 개수 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에는 초기 $i$번째 어린이가 속한 모둠 번호 $C_i$가 공백으로 구분되어 주어진다.

세 번째 줄에는 쿼리의 개수 $Q$가 주어진다.

네 번째 줄부터 $Q$개의 줄에는 쿼리를 나타내는 정수들이 공백으로 구분되어 주어진다.

$3$번 쿼리가 주어질 때마다 정답을 줄 바꿈으로 구분하여 출력한다.

• $1 \le N, K, Q \le 10^6$
• $1 \le C_i \le K$ $(1 \le i \le N)$
• $1$번 쿼리에서 $1 \le i \le N;\ 1 \le c \le K$
• $2$번 쿼리에서 $1 \le c \le K;\ -1\, 000 \le x \le 1\, 000$
• $3$번 쿼리에서 $1 \le i \le N$

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 다음은 대표적인 언어에서 빠른 입출력을 이용하는 방법입니다.

• C++: cin, cout 을 사용한다면 main 함수 첫 줄에 std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios\_base::sync\_with\_stdio(false); 를 추가하고, 줄바꿈 시 std::endl 대신 '\n' 을 출력해 주세요. 이 경우 scanf 를 비롯한 C의 입출력 함수는 사용할 수 없음에 유의해 주세요.
  • scanf / printf 는 충분히 빠르므로 별도의 처리를 하지 않아도 괜찮습니다.
• Java: Scanner 와 System.out.println 대신 BufferedReader 와 BufferedWriter 를 사용해 주세요.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip() 을 사용해 주세요.