There is a self-driving taxi in Innopolis that drives on a long street. The street consists of $n+1$ taxi stops and $n$ segments connecting adjacent stops. There is a street lamp on each segment. The $i$-th lamp illuminates the segment connecting stop $i$ and $i+1$, if the lamp is on. Otherwise, it's dark on the segment.

For the purpose of safety the self-driving taxi can only drive on the segments that are illuminated. In other words, the taxi can drive from the stop $a$ to the stop $b$ $(a<b)$, if the segments between $a$ and $a+1$, $a+1$ and $a+2$, …, $b-1$ and $b$ are illuminated.

After breakdowns or repairs the street lamps can turn on or turn off. You are given the initial state of the lamps at the moment $0$. After that in the end of hours $1,2,\dots ,q$ events take place. Exactly one event takes place in the end of each hour, there are two types of events:

• toggle i — the $i$-th lamp changes its state: if the lamp was on, it turns off, if the lamp was off, it turns on.
• query a b — the head of the self-driving taxi department wonders, what is the total time in hours from $0$ up to the current time when the taxi was able to drive from stop $a$ to stop $b$.

Help the head of self-driving taxi department to answer the questions.

Input

The first line contains two integers $n$ and $q$ $(1\le n,q\le 300000)$ — the number of street lamps and number of events.

The second line contains a string $s$ that describes the initial state of the lamps $(|s|=n)$, $s_i$ is 1 if the $i$-th lamp is on, and $s_i$ is 0 if the $i$-th lamp is off.

Each of the following $q$ lines describes events. The $i$-th of these lines describes an event that takes place in the end of the hour $i$.

• toggle i $(1\le i\le n)$ — the $i$-th lamp changes its state.
• query a b $(1\le a<b\le n+1)$ — calculate the number of hours until the current moment when the taxi was able to drive from stop $a$ to stop $b$.

At least one of the events is query.

Output

For each query event print a single integer: the answer to the question.

Scoring

Subtask 1 (points: 20)

$n\le 100,q\le 100$.

Subtask 2 (points: 20)

For all query a b events $b-a=1$.

Subtask 3 (points: 20)

For all toggle i events the $i$-th lamp is turning on.

Subtask 4 (points: 20)

All toggle events happen before all query events.

Subtask 5 (points: 20)

No additional constraint.

Sample Input

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

Sample Output

1
2
0
0
1
2

Explanation

In the sample test:

Hour	Lamp states	Query	Answer
$1$	$11011$	query 1 2	$1$
$2$	$11011$	query 1 2	$1$ and $2$
$3$	$11011$	query 1 6	None
$4$	$11011$	query 3 4	None
$5$	$11011$	toggle 3
$6$	$11111$	query 3 4	$6$
$7$	$11111$	query 1 6	$6$ and $7$