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 300\,000)~ — 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~