가로등

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

보안 문제로, 자율 주행 택시는 가로등이 켜진 도로만 달릴 수 있다. 다른 말로 하면, 택시가 정류장 a에서 정류장 b로 가려면 (a < b), 정류장 a과 정류장 a + 1를 잇는 도로, 정류장 a + 1과 정류장 a + 2를 잇는 도로, . . . , 정류장 b − 1과 정류장 b를 잇는 도로의 가로등이 켜져야 한다.

고장이 나거나, 수리를 하면 가로등이 켜지거나 꺼질 수 있다.

시점 0에서는 가로등의 초기 상황이 주어진다. 1, 2, . . . , q 시간이 지나면 다음 두 상황 중 하나가 벌어질 수 있다.

• “toggle i” — i 번 가로등이 반전된다. 즉, 이 가로등이 켜져 있었다면 꺼지고, 꺼져 있었다면 켜진다.
• “query a b” — 자율 주행 택시를 운영하는 곳의 대표가 다음을 궁금해한다. 시점 0에서 시작해서 현재에 이르기 까지 자율 주행 택시가 정류장 a에서 정류장 b까지 운행할 수 있었던 총 시간은 얼마일까?

자율 주행 택시를 운영하는 곳이 이 질의를 답하는 것을 도와주자

첫 번째 줄에는 두 정수 n, q가 주어진다. (1 ≤ n, q ≤ 300 000) — 이는 가로등의 수와 이벤트의 개수이다.

두번째 줄에는 최초의 가로등 상태를 알려주는 문자열 s가 주어진다. (|s| = n), 만약 가로등 i가 켜져 있으면 si는 ‘1’이고, 가로등 i가 꺼져 있으면 si는 ‘0’이다.

다음 q 줄 각각은 이벤트를 설명한다. 이 중 i 번째 줄은 i 시간이 지났을 때 이벤트를 설명한다.

• “toggle i” (1 ≤ i ≤ n) — 가로등 i이 반전된다.
• “query a b” (1 ≤ a < b ≤ n + 1) — 정류장 a에서 정류장 b까지 자율 주행 택시가 운행할 수 있었던 총 시간 수를 계산한다.

이벤트 중 최소 하나는 query이다.

각각의 query 이벤트마다 하나의 정수를 출력하고, 이 수는 질의에 대한 답이다.

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