Damage String Game

AKN is playing a new game and found a pattern in the damage calculation mechanism. You are given a binary string of length \(n\) (containing only characters '0' and '1') where the first character is at index \(1\). The game supports two types of operations:

• Query Operation (type = 1): Given a range \([l, r]\), the damage is defined as the number of '1's in that range.
• Modify Operation (type = 2): Given a range \([l, r]\), flip every bit in that range (i.e. change '0' to '1' and '1' to '0').

Your task is to process \(q\) operations and output the damage for each query operation.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\) representing the length of the damage string and the number of operations respectively.

The second line contains a binary string of length \(n\) representing the initial damage string.

The following \(q\) lines each contain three integers: \(t\), \(l\), and \(r\) \((1 \le l \le r \le n)\).
If \(t = 1\), perform a query operation by counting the number of '1's in the range \([l, r]\).
If \(t = 2\), perform a modify operation that flips every character in the range \([l, r]\).

outputFormat

For each query operation (when \(t = 1\)), output the damage (the number of '1's) in the given range in a new line.

sample

5 5
10101
1 1 5
2 2 4
1 1 3
2 3 5
1 1 5

3
2
3