가로등

이노폴리스에서는 자율 주행 택시가 운행하고 있다. 이 도시의 도로망은 택시를 탈 수 있는 정류장 $n+1$개와 이들을 잇는 도로 $n$개로 이루어진다. 도로마다 가로등이 하나씩 있다. $i$번 가로등이 켜져 있으면 정류장 $i$와 정류장 $i+1$을 잇는 도로를 밝힌다. 꺼져 있으면 이 도로는 어둡다.

보안 문제로 자율 주행 택시는 가로등이 켜진 도로만 달릴 수 있다. 즉, 택시가 정류장 $a$에서 정류장 $b$로 가려면($a < b$), 정류장 $a$와 $a+1$을 잇는 도로부터 정류장 $b-1$과 $b$를 잇는 도로까지 가로등이 모두 켜져 있어야 한다.

가로등은 고장이 나거나 수리되면서 켜지거나 꺼질 수 있다.

시점 0에는 가로등의 초기 상태가 주어진다. 시점 $1, 2, \ldots, q$마다 다음 두 가지 중 하나가 일어난다.

• toggle i: $i$번 가로등의 상태를 반전한다. 켜져 있었다면 꺼지고, 꺼져 있었다면 켜진다.
• query a b: 자율 주행 택시를 운영하는 곳의 대표가 궁금해한다. 시점 0부터 현재까지 택시가 정류장 $a$에서 정류장 $b$까지 운행할 수 있었던 총 시간은 얼마인가?

이 질의에 답하는 것을 도와주자.

첫 줄에 두 정수 $n$, $q$가 주어진다 ($1 \le n, q \le 300\,000$). 각각 가로등의 수와 이벤트의 개수이다.

둘째 줄에는 최초 가로등 상태를 나타내는 문자열 $s$가 주어진다 ($|s| = n$). $s_i$가 1이면 가로등 $i$가 켜져 있고, 0이면 꺼져 있다.

다음 $q$개의 줄에는 이벤트가 하나씩 주어진다. $i$번째 줄은 $i$ 시간에 일어난 이벤트를 설명한다.

• toggle i ($1 \le i \le n$): 가로등 $i$의 상태를 반전한다.
• query a b ($1 \le a < b \le n+1$): 정류장 $a$에서 정류장 $b$까지 택시가 운행할 수 있었던 총 시간 수를 구한다.

이벤트 중 적어도 하나는 query이다.

각 query 이벤트마다 답을 나타내는 정수를 한 줄에 하나씩 출력한다.

예제 입력의 결과는 다음과 같다.