Problem Description

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

• The player whose turn it is takes the piece and moves it to 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 the player $\textbf{must}$ move the piece.
• After moving the piece to some cell $y$, the player adds $A_y$ to her score. Note that the score is added $\textbf{after}$ moving the piece.

The moves alternate between the two girls and Klimi plays first. The game ends in exactly $10^{100}$ 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 $\verb|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 $\verb|updateValue|$ and $\verb|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 $\verb|init|$.

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

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

Your program must implement the three functions, but should not contain a function $\verb|main|$. Also, it must not read from the standard input or print to the standard output. Your program must also include the header file $\verb|game.h|$ by an instruction to the preprocessor: $\verb|#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 $\verb|Lgrader.cpp|$ and $\verb|game.h|$, which you can compile together with your code to test it.

Input Format

The input format of the grader is:

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

Where the format of the queries is:

• $1$ $\verb|ind|$ $\verb|val|$ --- Update query setting $A_{\mathrm{ind}}=\mathrm{val}$
• $2$ $\verb|ind|$ --- Question query for the piece starting in $\verb|ind|$

Output Format

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

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

1
0
0
1

Hint

Example

Suppose $A = [1, 7, 4, 9, 30, 2]$, $D = 2$, and $Q = 5$. An example sequence of calls is:

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

The array after the update call is $[1, 7, 4, 9, 8, 2]$. It can be shown that those are the correct answers to the questions if both girls play optimally.

Constraints

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

Subtasks

You must pass all tests in a subtask to get the points.