| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 37 | 24 | 23 | 74.194% |
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의 종이에 적힌 수들 | 설명 |
| 게임 시작 직후 | 2, 4, 6, 8, 10 | |
| 1번째 요청 직후 | 2, 4, 6, 8, 10 | $A_1 = 2 + 4 + 6 = 12$ |
| 2번째 요청 직후 | 2, 4, 6, 8, 10 | $A_2 = 10 + 8 + 6 = 24$ |
| 3번째 요청 직후 | 2, 3, 4, 6, 8, 10 | 3을 추가했다. |
| 4번째 요청 직후 | 2, 3, 4, 6, 7, 8, 10 | 7을 추가했다. |
| 5번째 요청 직후 | 2, 3, 4, 6, 7, 8, 10 | $A_5 = 2 + 3 + 4 = 9$ |
| 6번째 요청 직후 | 2, 3, 4, 6, 7, 8, 10 | $A_6 = 10 + 8 + 7 = 25$ |
| 7번째 요청 직후 | 7, 8, 9, 11, 12, 13, 15 | 모든 수에 5를 더했다. |
| 8번째 요청 직후 | 7, 8, 9, 11, 12, 13, 15 | $A_8 = 7 + 8 + 9 = 24$ |
| 9번째 요청 직후 | 7, 8, 9, 11, 12, 13, 15 | $A_9 = 15 + 13 + 12 = 40$ |
| 10번째 요청 직후 | 1, 7, 8, 9, 11, 12, 13, 15 | 1을 추가했다. |
| 11번째 요청 직후 | 1, 7, 8, 9, 11, 12, 13, 15 | $A_{11} = 15 + 13 + 12 + 11 = 51$ |
| 12번째 요청 직후 | 1, 7, 8, 9, 11, 12, 13, 15 | $A_{12} = 1 + 7 + 8 + 9 = 25$ |
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번 요청을 하면 입력 제한 마지막 조건을 어기게 되기 때문이다.
| 시점 | Albert의 종이에 적힌 수들 | 설명 |
| 게임 시작 직후 | 1, 1, 1, 1, 500000 | |
| 1번째 요청 직후 | 1, 1, 1, 1, 500000 | $A_1 = 1 + 1 + 1 + 1 + 500000 = 500004$ |
| 2번째 요청 직후 | 1, 1, 1, 1, 500000 | $A_2 = 500000 + 1 + 1 + 1 = 500004$ |
| 3번째 요청 직후 | 100001, 100001, 100001, 100001, 600000 | 모든 수에 100000을 더했다. |
| 4번째 요청 직후 | 100001, 100001, 100001, 100001, 600000 | $A_4 = 100001 + 100001 + 100001 = 300003$ |
| 5번째 요청 직후 | 100001, 100001, 100001, 100001, 600000 | $A_5 = 600000 + 100001 + 100001 = 800002$ |
| 6번째 요청 직후 | 500001, 500001, 500001, 500001, 1000000 | 모든 수에 400000을 더했다. |
| 7번째 요청 직후 | 500001, 500001, 500001, 500001, 1000000 | $A_7 = 500001 + 500001 + 500001 = 1500003$ |
| 8번째 요청 직후 | 500001, 500001, 500001, 500001, 1000000 | $A_8 = 1000000 + 500001 + 500001 = 2000002$ |