Illuminated Path Queries

An autonomous taxi is driving the streets of Innopolis. The street has \(n+1\) parking stations dividing the street into \(n\) segments. Each segment is equipped with a street light. When the \(i\)-th street light is on, it illuminates the segment connecting station \(i\) and station \(i+1\); otherwise, the segment is dark.

For safety reasons, the taxi can only travel along illuminated segments. In other words, the taxi can travel from station \(a\) to station \(b\) (with \(a < b\)) if and only if every street light on segments \(a, a+1, \ldots, b-1\) is on.

Initially, at time 0, you are given the status of all \(n\) street lights. Then, at times \(1, 2, \ldots, q\), one of the following two events occurs:

• toggle i: Toggle the state of the \(i\)-th street light. (If it was on, it turns off; if it was off, it turns on.)
• query a b: The taxi department wants to know, from time 0 up to the current time, how many moments in time satisfy that the taxi can travel from station \(a\) to station \(b\) (i.e. segments \(a\) to \(b-1\) are all illuminated).

Please help answer these queries.

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space, where \(n\) is the number of street lights and \(q\) is the number of events.

The second line contains a string of length \(n\) consisting of characters '0' and '1'. The \(i\)-th character denotes the initial state of the \(i\)-th street light ('1' means on, '0' means off) at time 0.

Each of the following \(q\) lines contains an event in one of the following formats:

• toggle i — toggle the \(i\)-th street light (1-indexed).
• query a b — query how many moments in time from time 0 to the current time (inclusive) satisfy that the taxi can travel from station \(a\) to station \(b\) (with \(a < b\)).

outputFormat

For each query event, output a single integer on a new line, representing the answer to that query.

sample

5 5
10101
query 1 3
toggle 2
query 1 3
toggle 1
query 2 5

0
1
0