#define NDEBUG
#include <bits/stdc++.h>
using namespace std;
#pragma region debug
#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '[';
if (v.size()) {
os << *v.begin();
for (auto i = ++v.begin(); i != v.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
os << '[';
if (d.size()) {
os << *d.begin();
for (auto i = ++d.begin(); i != d.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
os << '[';
if (s.size()) {
int n = s.size();
vector<T> v(n);
for (int i = 0; i < n; i++) {
v[i] = s.top();
s.pop();
}
os << v[n - 1];
for (int i = n - 2; i >= 0; i--) {
os << ", " << v[i];
}
}
return os << "]>";
}
template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
os << '[';
if (q.size()) {
int n = q.size();
vector<T> v(n);
for (int i = 0; i < n; i++) {
v[i] = q.front();
q.pop();
}
os << v[n - 1];
for (int i = n - 2; i >= 0; i--) {
os << ", " << v[i];
}
}
return os << "]>";
}
template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
os << '[';
if (N) {
os << *a.begin();
for (auto i = ++a.begin(); i != a.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
os << '[';
if (m.size()) {
os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
for (auto i = ++m.begin(); i != m.end(); i++)
os << ", " << '(' << i->first << " : " << i->second << ')';
}
return os << ']';
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const unordered_map<T1, T2> &m) {
os << '[';
if (m.size()) {
os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
for (auto i = ++m.begin(); i != m.end(); i++)
os << ", " << '(' << i->first << " : " << i->second << ')';
}
return os << ']';
}
#define dbg1(a) \
if ((#a)[0] == '\"') { \
if ((#a) == "\"_h1\"") \
cerr << "--------------------------------\n"; \
else if ((#a) == "\"_h2\"") \
cerr << "================================\n"; \
else if ((#a) == "\"_h3\"") \
cerr << "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡\n"; \
else if ((#a) == "\"_h4\"") \
cerr << "################################\n"; \
else \
cerr << a; \
} else { \
cerr << #a << " = " << a << '\n'; \
}
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg8, dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif
#pragma endregion debug
template<class Base>
class Segtree : public Base {
using T = typename Base::T;
using Base::dval;
using Base::merge;
using Base::apply;
protected:
size_t n;
struct node {
T v;
int l, r;
node() = default;
node(T _v, int _l, int _r) : v(_v), l(_l), r(_r) {}
};
int root;
vector<node> tree;
size_t new_node() {
tree.emplace_back(dval, -1, -1);
return tree.size() - 1;
}
private:
void update(int i, T v, int t, int tl, int tr) {
if (tl == tr) {
apply(tree[t].v, v);
return;
}
int tm = (tl + tr) / 2;
if (i <= tm) {
if (tree[t].l == -1)
tree[t].l = new_node();
update(i, v, tree[t].l, tl, tm);
} else {
if (tree[t].r == -1)
tree[t].r = new_node();
update(i, v, tree[t].r, tm + 1, tr);
}
tree[t].v = merge(tree[t].l == -1 ? dval : tree[tree[t].l].v, tree[t].r == -1 ? dval : tree[tree[t].r].v);
}
T query(int l, int r, int t, int tl, int tr) {
if (r < tl || tr < l)
return dval;
if (l <= tl && tr <= r)
return tree[t].v;
int tm = (tl + tr) / 2;
return merge(tree[t].l == -1 ? dval : query(l, r, tree[t].l, tl, tm), tree[t].r == -1 ? dval : query(l, r,
tree[t].r, tm + 1, tr));
}
public:
Segtree() = default;
Segtree(size_t _n) {
init(_n);
}
void init(size_t _n) {
n = _n;
root = new_node();
}
void reserve(size_t _n) {
tree.reserve(_n);
}
void clear() {
tree.clear();
}
void update(int i, T v) {
update(i, v, root, 0, n - 1);
}
T query(int l, int r) {
return query(l, r, root, 0, n - 1);
}
};
struct stinfo {
using T = int;
const T dval = 0;
void apply(T &a, T b) {
a += b;
}
T merge(T a, T b) {
return a + b;
}
};
class Fentree {
size_t n;
vector<Segtree<stinfo>> tree;
public:
Fentree() = default;
Fentree(size_t _n) {
init(_n);
}
void init(size_t _n) {
n = _n;
tree.resize(n + 1);
for (int i = 1; i <= n; i++)
tree[i].init(n);
}
void update(int i, int j, int v) {
// dbg("_h2", "updated:\n", i, j, v);
for (i++; i <= n; i += i & -i)
tree[i].update(j, v);
}
int query(int i, int l, int r) {
int ret = 0;
for (i++; i; i -= i & -i)
ret += tree[i].query(l, r);
return ret;
}
int query(int i, int j, int l, int r) {
return query(j, l, r) - query(i - 1, l, r);
}
};
int main() {
int N, Q;
string S;
cin >> N >> Q >> S;
set<int> off;
Fentree bit(N + 1);
for (int i = 0; i < N; i++) {
if (S[i] == '0') {
auto [it, b] = off.insert(i);
int r = *it - 1;
int l = (it == off.begin() ? 0 : *prev(it) + 1);
// update [l, r] x [l, r]
dbg("_h4", "square update\n", l, r, l, r);
bit.update(l, l, Q);
bit.update(r + 1, l, -Q);
bit.update(l, r + 1, -Q);
bit.update(r + 1, r + 1, Q);
} else if (i == N - 1) {
int r = N - 1;
int l = (off.empty() ? 0 : *prev(off.end()) + 1);
// update [l, r] x [l, r]
dbg("_h4", "square update\n", l, r, l, r);
bit.update(l, l, Q);
bit.update(r + 1, l, -Q);
bit.update(l, r + 1, -Q);
bit.update(r + 1, r + 1, Q);
}
}
//dbg(off);
for (int q = 1; q <= Q; q++) {
string t;
cin >> t;
if (t == "query") {
int l, r;
cin >> l >> r;
l--, r -= 2;
if (off.lower_bound(l) == off.upper_bound(r)) {
dbg("_h4", "query v1:\n", l, r, bit.query(0, l, 0, r), q);
cout << bit.query(0, l, 0, r) - (Q - q) << '\n';
} else {
dbg("_h4", "query v2:\n", l, r, bit.query(0, l, 0, r), q);
cout << bit.query(0, l, 0, r) << '\n';
}
} else if (t == "toggle") {
int k;
cin >> k;
k--;
if (S[k] == '0') {
S[k] = '1';
off.erase(k);
auto itl = off.lower_bound(k);
int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
auto itr = off.upper_bound(k);
int r = (itr == off.end() ? N - 1 : *itr - 1);
// update [l, k] x [k, r]
dbg("_h4", "square update\n", l, k, k, r, Q - q);
bit.update(l, k, Q - q);
bit.update(l, r + 1, q - Q);
bit.update(k + 1, k, q - Q);
bit.update(k + 1, r + 1, Q - q);
} else {
S[k] = '0';
auto itl = off.lower_bound(k);
int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
auto itr = off.upper_bound(k);
int r = (itr == off.end() ? N - 1 : *itr - 1);
off.insert(k);
// update [l, k] x [k, r]
bit.update(l, k, q - Q);
bit.update(l, r + 1, Q - q);
bit.update(k + 1, k, Q - q);
bit.update(k + 1, r + 1, q - Q);
}
}
}
}
