Hide

# Problem KPönnukökur

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

Hide