Problem Description

Zhang San and Li Si are playing a game. The rules are as follows.

In front of them there is a board. The board is a cycle consisting of $n$ nodes and $n$ edges, and each edge has a weight. Initially, a piece is placed on some node. Zhang San and Li Si take turns moving the piece, with Zhang San moving first. Whoever cannot make a move loses. Each move must choose a neighbor of the current node (i.e., a node connected by an edge), move the piece along that edge to the neighbor, and decrease the edge weight by any positive integer. Note that an edge weight is not allowed to be decreased to a negative number.

Zhang San wants you to compute, for a given board, how many initial positions of the piece allow him to have a winning strategy.

Now you are given a sequence $a_1,a_2,\dots,a_m$ of length $m$, and you need to perform $q$ operations. Each operation is one of the following.

• 1 x y means assigning $a_x$ to $y$.
• 2 l r means querying: if the board has $(r-l+1)$ nodes in total, and the edge weights in clockwise order are $a_l,a_{l+1},\dots,a_r$, then for this game, how many different initial piece positions allow Zhang San to have a winning strategy.

Input Format

There are $q+2$ lines in total.

The first line contains two positive integers $m,q$.

The second line contains $m$ integers, where the $i$-th number is $a_i$.

The next $q$ lines each contain three integers, in the format described in the statement.

Output Format

Output several lines. Each line contains one non-negative integer, representing the answer to one query.

6 7
0 1 0 2 3 0
2 1 6
1 1 1
2 1 6
2 4 5
1 4 3
2 3 5
2 4 5

3
2
2
1
0

见选手目录下的 ring/ring2.in 与 ring/ring2.ans。

见选手目录下的 ring/ring2.in 与 ring/ring2.ans。

Hint

Subtasks

For all testdata, it is guaranteed that $1 \le m,q \le 3 \times 10^5$, $1 \le l \le r \le m$, $1\le x \le m$, and $0 \le y,a_i \le 10^6$.

Special property A: it is guaranteed that $0 \le y,a_i \le 1$.

Special property B: it is guaranteed that all queries satisfy $l=1$ and $r=m$.

Special property C: it is guaranteed that there are no modification operations.

Translated by ChatGPT 5