Problem Description

There is a sequence of length $n$.

And $Q$ queries are given.

For each query, $q_i$ is given.

• When $q_i$ is $1$, invert the bits in the range $l_i \leq i < r_i$.
• When $q_i$ is $2$, output the number of $1$'s in the range $l_i \leq i < r_i$.

Write a program to process such queries.

Note that the initial value is $0$ at all positions, and the first position is considered as $0$.

For example, if $n=7$ and $q_i, l_i, r_i$ are as follows, the state of the bits will be as follows:

{$ q_i,l_i,r_i $} 0 0 0 0 0 0 0 Output {1,2,5} 0 0 1 1 1 0 0 - {1,4,7} 0 0 1 1 0 1 1 - {2,1,6} 0 0 1 1 0 1 1 3 {1,0,4} 1 1 0 0 0 1 1 - {2,3,7} 1 1 0 0 0 1 1 2 {1,2,6} 1 1 1 1 1 0 1 - {2,0,7} 1 1 1 1 1 0 1 6 Therefore, the output will be as follows:

```
3
2
6

## Input Format

The input is given from the standard input in the following format:

> $ n $ $ Q $ $ q_1 $ $ l_1 $ $ r_1 $ $ : $ $ : $ $ : $ $ q_Q $ $ l_Q $ $ r_Q $

- The first line contains the length of the sequence $n$ and the number of queries $Q$, separated by spaces.
- From the second line to the $Q+1$th line, $q_i, l_i, r_i$ are given separated by spaces.
- $q_i$ is the type of query, and $l_i, r_i$ are the left and right positions, respectively.
- Note that the range to be considered (or inverted) is up to the position right before the right end.

## Output Format

The output should follow the standard output in the following format:

- For each output query, output the number of $1$'s in the range $l_i \leq \text{position} < r_i$.
- Do not forget to add a newline after each query.

## Sample Input and Output

### Sample Input #1

8 4
1 3 7
2 2 5
1 2 4
2 1 6

### Sample Output #1

2
3

### Sample Input #2

5 3
1 0 3
1 2 5
2 1 4

### Sample Output #2

2

### Sample Input #3

7 7
2 3 4
1 4 6
2 1 5
1 0 7
1 2 5
2 0 7
1 2 3

### Sample Output #3

0
1
4
```

Notes/Hints

Constraints

• $1 \leq n, Q \leq 100,000$
• $0 \leq l_i < r_i \leq n$
• $1 \leq q_i \leq 2$

Subtasks

Subtask $1$ \[ $4$ points \]

• Satisfies $1 \leq n, Q \leq 1,000$.

Subtask $2$ \[ $12$ points \]

• The number of output queries is within $1,000$.

Subtask $3$ \[ $36$ points \]

• The output queries have $l_i, r_i$ as $0, n$ respectively.

Subtask $4$ \[ $48$ points \]

• No additional constraints.

Sample Explanation 1

The values of the sequence change as follows: {$ q_i,l_i,r_i $} 0 0 0 0 0 0 0 0 Output {1,3,7} 0 0 0 1 1 1 1 0 - {2,2,5} 0 0 0 1 1 1 1 0 2 {1,2,4} 0 0 1 0 1 1 1 0 - {2,1,6} 0 0 1 0 1 1 1 0 3

Sample Explanation 2

The values of the sequence change as follows: {$ q_i,l_i,r_i $} 0 0 0 0 0 Output {1,0,3} 1 1 1 0 0 - {1,2,5} 1 1 0 1 1 - {2,1,4} 1 1 0 1 1 2

见题面 Input 部分

见题面 Output 部分