| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 32 | 21 | 20 | 76.923% |
Albert는 정수 덧셈을 연습하고 있다. 이를 지켜보던 Bobby는 연습을 좀 더 재미있게 해주려고 아래와 같은 게임을 제안했다.
예를 들어 $N = 5,ドル $V = [2, 4, 6, 8, 10],ドル $M = 12,ドル $Q = [4, 3, 1, 1, 4, 3, 2, 4, 3, 1, 3, 4]$ 그리고 $W = [3, 3, 3, 7, 3, 3, 5, 3, 3, 1, 4, 4]$ 라 하자. 이 경우 아래 표에서 각 요청 이후 Albert가 어떤 수들을 갖고 있는지 확인할 수 있다.
Albert는 신나서 이 게임을 하기로 했는데, 막상 Bobby는 게임을 제안했지만 준비가 되지 않았다. Bobby는 당신의 도움을 받아 Albert가 더해낸 값들이 맞는지(위 예제에서 $A_1, A_2, \dots, A_{11}, A_{12}$ 등의 값) 확인해 달라고 부탁했다. 즉, $Q_{j} \in \{3, 4\}$인 경우에 대해 올바른 $A_j$ 값을 구해서 Bobby에게 알려주자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 두 정수 $N, M$이 공백으로 구분되어 주어진다. 둘째 줄에는 $V_1, V_2, \dots, V_N$을 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다. 다음 $M$줄에 걸쳐 각 줄에 $Q_j, W_j$ 두 개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답이 되는 $A_j$ 값을 각 줄에 공백으로 구분하여 출력한다. 단, 입력으로 주어진 $Q_j$ 값이 3 혹은 4인 경우에만 $A_j$값을 구하면 된다.
2 5 12 2 4 6 8 10 4 3 3 3 1 3 1 7 4 3 3 3 2 5 4 3 3 3 1 1 3 4 4 4 5 8 1 1 1 1 500000 4 5 3 5 2 100000 4 3 3 3 2 400000 4 3 3 3
12 24 9 25 24 40 51 25 500004 500004 300003 800002 1500003 2000002
예제 1: 본문에서 다루었다.
예제 2: 아래 표는 Alice의 각 요청 이후 게임 상태를 설명해준다. 참고로 6번째 요청 직후 더 이상 Alice는 2번 요청 (모든 수에 다른 수를 더하도록 하는 요청)을 할 수 없는데, 한 번 더 2번 요청을 하면 입력 제한 마지막 조건을 어기게 되기 때문이다.