Sequence and Queries 37

There is a sequence $A_1, A_2, \dots, A_N$ of length $N$. Write a program that performs the following queries.

• 1 i x: set $A_i$ to $x$.
• 2 l r: print the number of even values among all $A_i$ with $l \le i \le r$.
• 3 l r: print the number of odd values among all $A_i$ with $l \le i \le r$.

The sequence is indexed starting from 1.

The first line gives the size of the sequence $N$ ($1 \le N \le 100\,000$).

The second line gives $A_1, A_2, \dots, A_N$. ($1 \le A_i \le 10^9$)

The third line gives the number of queries $M$ ($1 \le M \le 100\,000$).

Each of the next $M$ lines gives one query. ($1 \le i \le N$, $1 \le l \le r \le N$, $1 \le x \le 10^9$)

Print the answers to queries of type 2 and 3, one per line.