Yin-Yang Fish Combination on a Tree Chain

A tree has nodes, each hanging a fish represented as either \(0\) (yin fish) or \(1\) (yang fish). Due to genetic mutations, any fish may mutate to the other type.

CleverRaccoon, carrying a basket that can hold up to \(2\) fish, walks along a certain chain on this tree. At each node, the following actions occur in order:

1. If the fish at the node is of opposite type to any fish in the basket (i.e. one is \(0\) and the other is \(1\)), he removes that fish from the basket, combines it with the fish at the node to create a yin-yang fish, and immediately eats it. (This counts as one eaten fish.)
2. If no combination is possible and the basket is not full (containing less than \(2\) fish), he places the fish from the node into the basket.
3. If the basket is full and no combination is possible, nothing happens at that node.

The problem involves two types of operations on this chain of nodes:

1. Mutation Operation: A fish at a specified node mutates. In other words, its type flips from \(0\) to \(1\) or from \(1\) to \(0\).
2. Query Operation: Given a segment of the chain defined by nodes \(L\) to \(R\) (inclusive), simulate CleverRaccoon's walk from \(L\) to \(R\) with an initially empty basket and report how many fish he eats.

Note that all indices are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(q\), representing the number of nodes in the chain and the number of operations, respectively.

The second line contains \(n\) integers, each either \(0\) or \(1\), representing the initial type of the fish at each node.

The next \(q\) lines each describe an operation. Each operation is in one of the following formats:

• 1 i: Mutation operation. Flip the fish type at node \(i\).
• 2 L R: Query operation. Simulate the process on the segment from node \(L\) to \(R\) (inclusive) and determine the number of fish eaten.

outputFormat

For each query operation (operation type 2), output the number of fish eaten, each on a new line.

sample

4 3
0 1 0 1
2 1 4
1 2
2 1 4

2
1