Piece Game

Klimi and Nikol have an integer array $A$ with $N$ cells numbered from $0$ to $N - 1$. The values in the array are all different.

The girls play a game with a single piece that is moved around the array. The piece starts in some cell. One move proceeds as follows:

1. The player whose turn it is moves the piece to another cell at distance at most $D$ from the current one. If the piece is in cell $x$ ($0 \le x < N$), the player may move it to cell $y$ ($0 \le y < N$) when $|y - x| \le D$ and $x \ne y$. A player must move the piece.
2. After moving the piece to cell $y$, the player adds $A_y$ to her score. The score is added after the move.

The moves alternate, and Klimi plays first. The game ends after exactly $10^{100}$ turns. The girl with the higher total score wins. If the scores are equal, Klimi wins.

The girls want to know the optimal results in several scenarios. You are given the initial array $A$ and the value $D$, and you must process $Q$ queries of two types:

• Update: a single value in the array is changed.
• Question: determine whether Klimi, who plays first, wins from a given initial position under optimal play.

Updates persist across queries, so each question uses all updates made so far.

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