Description

A self-driving taxi is driving along a street in Innopolis. There are $n+1$ stops on the street, which divide the street into $n$ road segments. Each segment has a street lamp. When the $i$-th lamp is on, it lights up the segment connecting stops $i$ and $i+1$. Otherwise, this segment is dark.

For safety reasons, the taxi can only drive on lit segments. In other words, the taxi can travel from stop $a$ to stop $b$ $(a<b)$ if and only if the segments connecting stops $a$ and $a+1$, $a+1$ and $a+2$, $\ldots$, $b-1$ and $b$ are all lit.

After some unexpected failures or repairs, the street lamps on the street may be on or off.

You are given the initial states of the street lamps at time $0$. Then at times $1,2,\ldots,q$, one of the following two events happens at each time:

• $\text{toggle}\ i$: Toggle the state of the $i$-th street lamp. Specifically, if it was on, it becomes off; if it was off, it becomes on.

• $\text{query}\ a\ b$: The head of the taxi department wants to know: from time $0$ up to the current time, how many times satisfy that the taxi can travel from stop $a$ to stop $b$.

Please help answer these queries for the head of the taxi department.

Input Format

The first line contains two integers $n$ and $q$, representing the number of street lamps and the number of time moments.

The second line contains a string $s$ representing the initial states of the street lamps. $s_i=1$ means the $i$-th lamp is initially on, and $s_i=0$ means the $i$-th lamp is initially off.

The next $q$ lines each describe the event at a time moment. The $i$-th of these lines describes the event that happens at time $i$:

• $\text{toggle}\ i$: At this time moment, the state of the $i$-th street lamp is toggled.

• $\text{query}\ a\ b$: Compute, from time $0$ up to this time moment, how many time moments satisfy that the taxi can travel from stop $a$ to stop $b$.

At least one event is $\text{query}$.

Output Format

For each $\text{query}$ event, output a single integer on its own line, which is the answer to that query.

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

1
2
0
0
1
2

Hint

For all data, $1 \leq n,q \leq 3\times 10^5$, $|s|=n$, $1 \leq i \leq n$, $1 \leq a < b \leq n+1$.

The detailed additional constraints and scores for subtasks are as follows.

Translated by ChatGPT 5