#include <bits/stdc++.h>
using namespace std;
struct fenwick {
int size;
vector<int> tree;
int sum;
vector<int> updates;
fenwick() {}
fenwick(int n) : size(n), tree(n + 1), sum(0) {}
void update(int i, int v) {
sum += v;
for (i++; i <= size; i += i & -i) {
updates.push_back(i);
tree[i] += v;
}
}
int prefix_query(int r) {
int ans = 0;
for (; r > 0; r -= r & -r) {
ans += tree[r];
}
return ans;
}
int suffix_query(int l) {
return sum - prefix_query(l);
}
void rollback() {
for (int i : updates) {
tree[i] = 0;
}
sum = 0;
updates = vector<int>();
}
};
struct query {
int x, y, tx, ty;
int pos;
};
struct modification {
int x, y, t;
};
fenwick F, Fc;
void CDQ(vector<query>& queries, vector<int>& answers, int L, int R) {
if (R - L == 1) {
return;
}
int M = (L + R) / 2;
CDQ(queries, answers, L, M);
CDQ(queries, answers, M, R);
{
vector<array<int, 4>> events;
for (int i = L; i < M; i++) {
if (queries[i].pos == -1) {
events.push_back({queries[i].y, queries[i].ty, 0, queries[i].ty - queries[i].tx});
}
}
for (int i = M; i < R; i++) {
if (queries[i].pos != -1) {
events.push_back({queries[i].y, queries[i].ty, 1, queries[i].pos});
}
}
sort(events.begin(), events.end(), [](array<int, 4> a, array<int, 4> b) {
return a[0] != b[0] ? a[0] > b[0] : (a[1] != b[1] ? a[1] < b[1] : a[2] < b[2]);
});
for (auto [y, ty, type, value] : events) {
if (type == 0) {
F.update(ty, value);
} else {
answers[value] += F.prefix_query(ty + 1);
}
}
F.rollback();
}
{
vector<array<int, 4>> events;
for (int i = L; i < M; i++) {
if (queries[i].pos == -1) {
events.push_back({queries[i].tx, 0, queries[i].y, -queries[i].tx});
events.push_back({queries[i].ty, -1, queries[i].y, queries[i].tx});
}
}
for (int i = M; i < R; i++) {
if (queries[i].pos != -1) {
events.push_back({queries[i].tx, 1, queries[i].y, queries[i].pos});
}
}
sort(events.begin(), events.end());
for (auto [x, type, y, value] : events) {
if (type <= 0) {
F.update(y, value);
Fc.update(y, type == 0 ? +1 : -1);
} else {
answers[value] += 1LL * Fc.suffix_query(y) * x + F.suffix_query(y);
}
}
F.rollback();
Fc.rollback();
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<modification> modifications;
set<pair<int, int>> segments;
int T = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
continue;
}
int j = i + 1;
while (j < n && s[j] == '1') {
j++;
}
modifications.push_back({i, j - 1, T});
segments.insert({i, j - 1});
i = j - 1;
}
vector<query> queries;
int cnt_q = 0;
while (q--) {
T++;
string type;
cin >> type;
if (type == "toggle") {
int pos;
cin >> pos;
pos--;
if (s[pos] == '0') {
s[pos] = '1';
if (segments.empty()) {
modifications.push_back({pos, pos, T});
segments.insert({pos, pos});
} else {
auto it = segments.lower_bound({pos, -1});
bool left_merge = it != segments.begin() && prev(it)->second == pos - 1;
bool right_merge = it != segments.end() && it->first == pos + 1;
if (left_merge && right_merge) {
int L = prev(it)->first, R = it->second;
modifications.push_back({prev(it)->first, prev(it)->second, T});
segments.erase({prev(it)->first, prev(it)->second});
modifications.push_back({it->first, it->second, T});
segments.erase({it->first, it->second});
modifications.push_back({L, R, T});
segments.insert({L, R});
} else if (left_merge) {
int L = prev(it)->first, R = pos;
modifications.push_back({prev(it)->first, prev(it)->second, T});
segments.erase({prev(it)->first, prev(it)->second});
modifications.push_back({L, R, T});
segments.insert({L, R});
} else if (right_merge) {
int L = pos, R = it->second;
modifications.push_back({it->first, it->second, T});
segments.erase({it->first, it->second});
modifications.push_back({L, R, T});
segments.insert({L, R});
} else {
modifications.push_back({pos, pos, T});
segments.insert({pos, pos});
}
}
} else {
s[pos] = '0';
auto it = prev(segments.lower_bound({pos, INT_MAX}));
int L = it->first, R = it->second;
modifications.push_back({L, R, T});
segments.erase({L, R});
if (L <= pos - 1) {
modifications.push_back({L, pos - 1, T});
segments.insert({L, pos - 1});
}
if (pos + 1 <= R) {
modifications.push_back({pos + 1, R, T});
segments.insert({pos + 1, R});
}
}
} else {
int a, b;
cin >> a >> b;
a--, b -= 2;
queries.push_back({a, b, T, T, cnt_q++});
}
}
sort(modifications.begin(), modifications.end(), [](modification a, modification b) {
return a.x != b.x ? a.x < b.x : (a.y != b.y ? a.y < b.y : a.t < b.t);
});
int m = (int)modifications.size();
T++;
for (int i = 0; i < m; i++) {
vector<int> times;
int j = i;
while (j < m && modifications[i].x == modifications[j].x && modifications[i].y == modifications[j].y) {
times.push_back(modifications[j++].t);
}
times.push_back(T);
for (int k = 0; k < (int)times.size() - 1; k += 2) {
queries.push_back({modifications[i].x, modifications[i].y, times[k], times[k + 1], -1});
}
i = j - 1;
}
F = Fc = fenwick(max(n, T) + 1);
vector<int> answers(cnt_q);
sort(queries.begin(), queries.end(), [](query a, query b) {
return a.x != b.x ? a.x < b.x : (a.y != b.y ? a.y > b.y : (a.tx != b.tx ? a.tx < b.tx : a.ty < b.ty));
});
CDQ(queries, answers, 0, (int)queries.size());
for (int value : answers) {
cout << value << "\n";
}
}
