Problem C
Pönnukökur
Languages
en
is
Signý is making pancakes. The pancakes have two sides, side $0$ and side $1$, and they have been arranged into a row. Thus what side faces up can be denoted by binary. Initially side $0$ faces up. Sometimes when she’s cooking the pancakes she flips them. If she flips a pancake with side $0$ facing up, then after the flip, side $1$ will face up, and vice versa. Signý is a bit odd and wants to know how many pancakes have side $1$ facing up in a particular interval. You are tasked with the job of keeping track of Signý’s flips and answering her questions.
Input
The first line contains two integers $n$ and $q$, the number of pancakes and number of operations. Next there are $q$ lines where each line describes one operation. There are four kinds of operations, the first integer in each line denotes what kind of operation it is.

Signý flips pancake $i$. The input is of the format 1 i, where $1 \leq i \leq n$.

Signý flips all pancakes. The input is of the format 2.

Signý asks how many pancakes have side $1$ facing upwards. The input is of the format 3.

Signý asks how many pancakes have side $1$ facing upwards from pancake $l$ to pancake $r$. The input is of the format 4 l r.
Output
For each question print a single integer, the answer to the question. The answers should come in the same order as the questions they answer.
Scoring
Group 
Points 
Constraints 
1 
20 
$1 \leq n,q \leq 2 \cdot 10^5$ only operations of types 1 and 3 
2 
14 
$1 \leq n,q \leq 2 \cdot 10^5$ only operations of types 1, 2 and 3 
3 
30 
$1 \leq n,q \leq 1000$ with all operations 
4 
36 
$1 \leq n,q \leq 2 \cdot 10^5$ with all operations 
Sample Input 1  Sample Output 1 

3 7 1 1 3 1 2 3 1 3 1 2 3 
1 2 2 
Sample Input 2  Sample Output 2 

2 5 3 1 1 2 3 3 
0 1 1 
Sample Input 3  Sample Output 3 

9 6 3 2 2 1 9 4 2 9 3 
0 1 1 