#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<int,int,int,int>;
#define assert kbjsadksja
string tmp;
void assert(bool ok) {
if(!ok) {
vector<int> v;
v.emplace_back(9);
while(1) v.resize(2 * sz(v), v.back() + sz(v));
}
}
void myassert(bool ok) {
if(!ok) {
exit(-1);
}
}
const int nmax = 3e5 + 5;
int last[nmax];
int rez[nmax];
vector<tii> upds[nmax];
vector<tiii> squares;
namespace Beats {
set<int> lends;
int rend[nmax];
int lval[nmax];
void init(int n, string s) {
int lst = 1;
for(int i = 1; i <= n; i++) {
if(s[i] == '0') {
if(i == lst);
else {
lends.emplace(lst);
rend[lst] = i - 1;
lval[lst] = 1;
}
lst = i + 1;
}
}
if(lst <= n) {
lends.emplace(lst);
rend[lst] = n;
lval[lst] = 1;
}
}
void reset(int p, int timer) {
auto it = lends.upper_bound(p);
myassert(it != lends.begin());
it = prev(it);
//cerr << p << '\t' << *it << ' ' << rend[*it] << '\n';
myassert(rend[*it] >= p);
squares.emplace_back(*it, rend[*it], lval[*it], timer - 1);
if(*it == p && rend[*it] == p)
lends.erase(it);
else if(*it == p && rend[*it] != p) {
rend[p + 1] = rend[*it];
lval[p + 1] = timer;
lends.erase(*it);
lends.emplace(p + 1);
}
else if(*it != p && rend[*it] == p) {
rend[*it]--;
lval[*it] = timer;
}
else if(*it != p && rend[*it] != p) {
rend[p + 1] = rend[*it];
rend[*it] = p - 1;
lends.emplace(p + 1);
lval[p + 1] = lval[*it] = timer;
}
}
void set(int p, int timer) {
auto nx = lends.upper_bound(p);
int l = p, r = p;
if(nx != lends.end()) {
if(*nx == p + 1) {
squares.emplace_back(*nx, rend[*nx], lval[*nx], timer - 1);
r = rend[*nx];
lends.erase(nx);
}
}
auto prv = lends.upper_bound(p);
if(prv != lends.begin()) {
prv = prev(prv);
if(rend[*prv] == p - 1) {
squares.emplace_back(*prv, rend[*prv], lval[*prv], timer - 1);
l = *prv;
lends.erase(prv);
}
}
lends.emplace(l);
rend[l] = r;
lval[l] = timer;
return;
}
void liquidate(int T) {
for(auto x : lends) {
squares.emplace_back(x, rend[x], lval[x], T);
}
}
void print() {
//for(auto x : lends)
//cerr << x << ", " << rend[x] << '\t';
//cerr << '\n';
}
}
#define lsb(x) (x & -x)
mt19937 rng(8283173);
template<typename T>
struct Treap {
struct Node {
Node *l, *r;
int pri;
T data;
} *nil = new Node {0, 0, 0, T()};
Treap() { nil -> l = nil -> r = nil; }
using ns = Node*;
struct pns { ns l, r; };
ns updnode(ns node, ns x, int t) {
(t == 0? node -> l : node -> r) = x;
node -> data.pull(node -> l -> data, node -> r -> data);
return node;
}
ns merge(ns l, ns r) {
return l == nil? r:
r == nil? l:
l -> pri > r -> pri? updnode(l, merge(l -> r, r), 1):
updnode(r, merge(l, r -> l), 0);
}
template<class CB> pns split(CB&& cb, ns node) { // here <= cst
pns tmp;
return node == nil? pns{nil, nil}:
cb(node -> data)? (tmp = split(cb, node -> r), tmp.l = updnode(node, tmp.l, 1), tmp):
(tmp = split(cb, node -> l), tmp.r = updnode(node, tmp.r, 0), tmp);
}
ns root = nil;
};
struct Val {
int poz;
int sum, mine;
void pull(const Val& x, const Val& y) { sum = x.sum + y.sum + mine; }
};
struct AIB : Treap<Val> {
void upd(int p, int x) {
auto [l, r] = split([&](Val& a) { return a.poz <= p; }, root);
root = merge(l, merge(new Node{nil, nil, rng(), Val{p, x, x}}, r));
}
int query(int p) {
auto [l, r] = split([&](Val& a) { return a.poz <= p; }, root);
int rnv = l -> data.sum;
root = merge(l, r);
return rnv;
}
};
struct AIB2D {
int n;
AIB tree[nmax];
void init(int n_) {
n = n_ + 1;
//for(int i = 1; i < n; i++) tree[i].N = n;
}
int query(int l, int r) {
int sum = 0;
while(l < n) sum += tree[l].query(r), l += lsb(l);
return sum;
}
void upd(int l, int r, int p) {
while(l > 0) tree[l].upd(r, p), l -= lsb(l);
}
void donefaking() {
//for(int i = 1; i < n; i++) tree[i].donefaking();
}
};
vector<pii> startsq[nmax], endsq[nmax];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<pii> qs;
string s;
cin >> s;
s = "#" + s;
for(int i = 1; i <= n; i++) last[i] = 1;
tmp = s;
Beats::init(n, s);
for(int i = 2; i <= q + 1; i++) {
string act;
cin >> act;
Beats::print();
//cerr << act << '\n';
if(act == "toggle") {
int x;
cin >> x;
if(s[x] == '1') Beats::reset(x, i);
else Beats::set(x, i);
s[x] ^= '1' ^ '0';
last[x] = i;
qs.emplace_back(-1, x);
}
else {
int l, r;
cin >> l >> r;
--r;
qs.emplace_back(l, r);
}
}
Beats::liquidate(q + 1);
//cerr << "---\n";
for(auto &[l, r, u, d] : squares) {
//cerr << l << ' ' << r << '\t' << u << ' ' << d << '\n';
startsq[u].emplace_back(l, r);
endsq[d + 1].emplace_back(l, r);
}
AIB2D deja;
deja.init(max(n, q) + 2);
for(int step = 0; step < 1; step++) {
s = tmp;
int timer = 1;
map<int, pii> opensq;
auto effectuate = [&](int i) {
for(auto [l, r] : endsq[i]) {
if(opensq.count(l)) {
deja.upd(r, l, i - opensq[l].second);
opensq.erase(l);
}
else assert(false); //???
}
for(auto [l, r] : startsq[i])
opensq[l] = make_pair(r, i);
return;
};
effectuate(1);
for(auto [l, r] : qs) {
timer++;
if(l == -1) {
int x = r;
s[x] ^= '1' ^ '0';
rez[timer] = -1;
}
else {
int standard = 0;
if(s[l] == '0' || s[r] == '0');// cerr << "fail\n";
else {
auto it = opensq.upper_bound(l);
assert(it != opensq.begin());
it = prev(it);
if(r <= it -> second.first)
standard += timer - it -> second.second;
}
rez[timer] = standard + deja.query(r, l);
}
if(timer != q + 1)
effectuate(timer);
}
deja.donefaking();
}
for(int i = 2; i <= q + 1; i++) {
if(rez[i] == -1) continue;
cout << rez[i] << '\n';
}
return 0;
}
/**
Binecuvanteaza Doamne Ukraina.
--
*/
