Game

Task

Klimi and Nikol have an integer array $A$ with $N$ cells numbered from $0$ to $N - 1$ and containing different integer values. The girls are playing a game played with a single piece that is moved around the array. Initially, the piece is located in the some cell. One move of the game proceeds as follows:

1. The player whose turn it is takes the piece and moves it in another cell that is at distance at most $D$ from the current one. Formally, if the piece is currently in cell $x$ ($0 \leq x < N$), then the player is allowed to move the piece to cell $y$ ($0 \leq y < N$) if $|y - x| \leq D$ and $x \neq y$. Note that this means a player must move the piece.
2. After moving the piece to some cell $y$, the player adds $A_y$ to her score. Note that the score is added after moving the piece.

The moves alternate between the two girls and Klimi plays first. The game ends in exactly $10100$ turns, at which point the girl whose total score is higher wins. If their score is equal, then Klimi wins.
The girls aren’t quite happy with the time it takes to finish even a single game, so they ask you to just figure out the optimal play results in different scenarios.
Formally, you will be given the initial array $A$ and the value $D$, and then you will have
to process $Q$ queries of two types:

• Updates: $A$ single value in the array is changed
• Questions: You are asked whether Klimi (the one to play first) wins the game, given some initial position of the piece and assuming optimal play.

The updates persist across queries, so each question must be answered considering all updates that have happened so far.
The implementation details section describes the interfaces you should support in more detail.

Implementation details

You must implement three functions. Your first function init must have the following prototype:

void init(std::vector<int> A, int D)

It will be called once in the beginning of the test and will supply you with the array $A$ and the value $D$.
Your other two functions updateValue and isWinning must have the following prototypes:

void updateValue(int index, int newValue)
bool isWinning(int startIndex)

The total number of calls to either of the two functions will be $Q$ (refer to the constraints section) and all calls will be done after the call to init.

The updateValue function must process an update query and set $A_{index}$ to $newValue$. It is guaranteed that after the updates all values in $A$ are still different.

The isWinning function must process a question query and return true if Klimi can win the game on the current array, given that the piece starts in cell $startIndex$. It must return false otherwise.

Your program must implement the three functions, but should not contain a function main. Also, it must not read from the standard input or print to the standard output. Your program must also include the header file game.h by an instruction to the preprocessor:

#include "game.h"

As long as it respects these conditions, your program can contain any helper functions, variables, constants, and so on.

Local testing

You are given the files Lgrader.cpp and game.h, which you can compile together
with your code to test it. The input format of the grader is:

• $N \ D$
• $A_0, A_1, \ldots A_{N-1}$
• $Q$
• <$Q$ lines of queries>

Where the format of the queries is:

• $1$ ind val — Update query setting $A_{ind} = val$
• $2$ ind — Question query for the piece starting in ind

For each query of type $2$, the grader will print $0$ if your function returned $false$ and $1$ if your function returned $true$

Constraints and clarifications

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq D \leq 25$
• $1 \leq A_i \leq 10^9$
• $0 \leq \text{index}, \text{startIndex} \leq N$
• $1 \leq \text{newValue} \leq 10^9$
• The values in $A$ are all different at all times, including after updates.

Subtasks

• Points for a given subtask are awarded only if all tests specified for it are successfully passed.

Example

Suppose $A = [1, 7, 4, 9, 30, 2]$, $D = 2$, ans $Q = 5$.

• Call to init({1, 7, 4, 9, 30, 2}, 2)
• Call to isWinning(0) which returns true
• Call to isWinning(1) which returns false
• Call to updateValue(4, 8)
• Call to isWinning(0) which returns false
• Call to isWinning(1) which returns true

Input

6 2
1 7 4 9 30 2
5
2 0
2 1
1 4 8
2 0
2 1

Output

1
0
0
1