게임

시간 제한1.5초메모리 제한1024 MB

요약

정수 배열과 이동 거리 제한 D가 주어질 때, 값을 바꾸는 갱신이 있는 상황에서 첫 번째 플레이어가 이기는지 판정합니다.

문제

클리미와 니콜은 $0$ 번부터 $N - 1$ 번까지 번호가 매겨진 $N$ 개의 칸으로 이루어진 정수 배열 $A$ 가 있다. 배열의 값은 모두 서로 다르다.

두 사람은 배열 위에서 말 하나를 옮기며 게임을 한다. 말은 처음에 어떤 칸에 놓여 있다. 한 번의 턴은 다음과 같이 진행된다.

차례인 사람이 말을 현재 칸에서 거리가 $D$ 이하인 다른 칸으로 옮긴다. 말이 $x$ 번 칸( $0 \le x < N$ )에 있을 때, $|y - x| \le D$ 이고 $x \ne y$ 이면 $y$ 번 칸( $0 \le y < N$ )으로 옮길 수 있다. 말은 반드시 옮겨야 한다.
말을 $y$ 번 칸으로 옮긴 뒤, 그 사람은 점수에 $A_y$ 를 더한다. 점수는 말을 옮긴 후에 더해진다.

턴은 번갈아 진행되며 클리미가 먼저 한다. 게임은 정확히 $10^{100}$ 번의 턴 뒤에 끝난다. 총점이 더 높은 사람이 이긴다. 점수가 같으면 클리미가 이긴다.

두 사람은 최적으로 두었을 때 결과가 어떻게 되는지 알고 싶어 한다. 주어진 $A$ 와 $D$ 에 대해 $Q$ 개의 질의를 처리해야 하며, 질의는 두 종류다.

갱신은 이후의 질의에도 계속 유지되므로, 각 질문은 지금까지의 모든 갱신을 반영한다.