Cycle Game: Winning Starting Positions

Two players, Zhangsan and Lisi, are playing the following impartial game on a circle. The circle consists of (n) nodes and (n) edges forming a cycle. Each edge (e_i) (for (i=1,2,\dots,n)) has a nonnegative integer weight (a_i). The edges are arranged in clockwise order. Initially, a token is placed on one of the nodes. The players take turns moving the token, with Zhangsan playing first. In a move, if the token is currently on a node, the player must choose one of its two adjacent nodes (i.e. there is an edge connecting the current node and the chosen node), then move the token along the corresponding edge, and subtract an arbitrary positive integer from that edge’s weight (the resulting weight must remain nonnegative). A player who cannot make a move loses.

It can be shown that, for a given cycle with edge weights (a_1,a_2,\dots,a_n) (listed in clockwise order), a token placed at node (i) (with the convention that node (1) has adjacent edges (a_n) and (a_1)) is winning for the first player if and only if [ a_{i-1} \oplus a_i \neq 0 \quad \text{(indices modulo }n\text{)}. ] Since (x\oplus y=0) if and only if (x=y) for nonnegative integers, the condition is equivalent to [ a_{i-1} \neq a_i. ]

Now you are given a sequence (a_1,a_2,\dots,a_m) of length (m). You need to process (q) operations. Each operation is one of the following two types:

1. “1 x y”: set (a_x) equal to (y).
2. “2 l r”: consider a cycle of (n=r-l+1) nodes where the edge weights in clockwise order are (a_l,a_{l+1},\dots,a_r). Determine how many choices of the initial token placement on this cycle (i.e. over the (n) nodes) yield a winning position for Zhangsan. (Recall that a token at node (i) is winning if and only if the two adjacent edge weights are different; note that when (i=l) the edge preceding it is (a_r) due to the cyclic order.)

You need to answer each query of type 2.

inputFormat

The first line contains two integers (m) and (q) (the length of the sequence and the number of operations).
The second line contains (m) integers (a_1,a_2,\dots,a_m), representing the initial edge weights.
Each of the following (q) lines contains an operation in one of the following forms:

• For an update operation: 1 x y
• For a query operation: 2 l r

outputFormat

For each query operation (i.e. lines beginning with 2), output a single integer — the number of nodes in the corresponding cycle at which the token’s placement is winning for the first player.

sample

5 5
1 1 2 2 3
2 1 5
1 3 1
2 2 4
1 5 2
2 1 5

3
1
2