Problem K
Pö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

3 7
1 1
3
1 2
3
1 3
1 2
3

1
2
2

2 5
3
1 1
2
3
3

0
1
1

9 6
3
2
2
1 9
4 2 9
3

0
1
1