Description

AKN thought the first problem was too easy and refused to write it, so he started a new game. In the game, he found a pattern in the damage calculation, as follows:

1. There is a damage string, which is a string of length $n$ consisting only of the characters 0 and 1. The first character is considered the first position, i.e., indices start from $1$.
2. Given a range $[l,~r]$, the damage is the number of characters 1 within that range of the damage string.
3. The damage string can be modified by toggling all characters in $[l,~r]$: change every 0 to 1 and every 1 to 0.

AKN wants to know the damage at certain times. Please help him compute it.

Input Format

The first line contains two integers separated by a space, representing the length $n$ of the damage string and the number of operations $m$.

The second line is a string $S$ of length $n$, representing the damage string.

From the $3$-rd to the $(m + 2)$-nd line, each line contains three integers $op, l, r$, representing the type and interval of the $i$-th operation. The rules are:

• If $op = 0$, toggle the characters in the interval $[l,~r]$ of the damage string: change 0 to 1 and 1 to 0.
• If $op = 1$, query how many characters 1 are in the interval $[l,~r]$ of the damage string.

Output Format

For each query, output a single line with one integer, representing the number of 1 in the interval.

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

3
6
1

Hint

Explanation for Sample Input/Output 1:

The original damage string is 1011101001.

For the first operation, toggle the characters in $[2,~4]$, and the damage string becomes 1100101001.

For the second operation, query the number of 1 in $[1,~5]$, which is $3$.

For the third operation, toggle the characters in $[3,~7]$, and the damage string becomes 1111010001.

For the fourth operation, query the number of 1 in $[1,~10]$, which is $6$.

For the fifth operation, toggle the characters in $[1,~4]$, and the damage string becomes 0000010001.

For the sixth operation, query the number of 1 in $[2,~6]$, which is $1$.

Constraints:

• For $10\%$ of the testdata, it is guaranteed that $n, m \leq 10$.
• For an additional $30\%$ of the testdata, it is guaranteed that $n, m \leq 2 \times 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $2 \leq n, m \leq 2 \times 10^5$, $0 \leq op \leq 1$, $1 \leq l \leq r \leq n$, and $S$ contains only the characters 0 and 1.

Translated by ChatGPT 5