There is a self-driving taxi in Innopolis that drives on a long street. The street consists of taxi
stops and
segments connecting adjacent stops. There is a street lamp on each segment. The
-th lamp
illuminates the segment connecting stop
and
, 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 to the stop
, if the segments between
and
,
and
, …,
and
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 . After that in the end of hours
events take place. Exactly one event
takes place in the end of each hour, there are two types of events:
toggle i
— the-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 fromup to the current time when the taxi was able to drive from stop
to stop
.
Help the head of self-driving taxi department to answer the questions.
Input
The first line contains two integers and
— the number of street lamps and number
of events.
The second line contains a string that describes the initial state of the lamps
,
is
1
if the -th lamp is on, and
is
0
if the -th lamp is off.
Each of the following lines describes events. The
-th of these lines describes an event that takes place
in the end of the hour
.
toggle i
— the
-th lamp changes its state.
query a b
— calculate the number of hours until the current moment when the taxi was able to drive from stop
to stop
.
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)
.
Subtask 2 (points: 20)
For all query a b
events .
Subtask 3 (points: 20)
For all toggle i
events the -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 |
---|---|---|---|
query 1 2 |
|||
query 1 2 |
|||
query 1 6 |
None | ||
query 3 4 |
None | ||
toggle 3 |
|||
query 3 4 |
|||
query 1 6 |
Comments
Since the original data were weak,
more tests cases were added to the last subtask, and the time limit was lowered from
s to
s.