Hide

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