#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>;
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) {
lends.emplace(1);
rend[1] = n;
lval[1] = 0;
}
void set(int l, int r, int a) {
auto it = lends.lower_bound(l);
if(it == lends.begin());
else {
it = prev(it);
if(rend[*it] >= r) {
int metar = rend[*it];
rend[*it] = l - 1;
squares.emplace_back(lval[*it], a, l, r);
lends.emplace(l);
rend[l] = r;
lval[l] = a;
if(metar > r) {
lends.emplace(r + 1);
rend[r + 1] = metar;
lval[r + 1] = lval[*it];
}
return;
}
squares.emplace_back(lval[*it], a, l, rend[*it]);
rend[*it] = l - 1;
}
while(1) {
it = lends.lower_bound(l);
if(it == lends.end()) break;
if(*it > r) break;
squares.emplace_back(lval[*it], a, max(l, *it), min(r, rend[*it]));
if(rend[*it] > r) {
lval[r + 1] = lval[*it];
rend[r + 1] = rend[*it];
lends.emplace(r + 1);
}
lends.erase(it);
}
lends.emplace(l);
lval[l] = a;
rend[l] = r;
return;
}
}
#define lsb(x) (x & -x)
struct AIB { // pt R-uri
int fake = 1;
map<int, int> atr;
vector<int> tree;
void upd(int p, int x) {
if(fake) {
atr[p];
return;
}
p = atr[p];
while(p < sz(tree)) tree[p] += x, p += lsb(p);
}
int query(int p) {
if(fake) {
//atr[p];
return 0;
}
auto it = atr.upper_bound(p);
if(it == atr.begin()) return 0;
p = prev(it) -> second;
int sum = 0;
while(p > 0) sum += tree[p], p -= lsb(p);
return sum;
}
void donefaking() {
int cnt = 0;
for(auto &[a, b] : atr) b = ++cnt;
tree.assign(cnt + 2, 0);
fake = 0;
return;
}
AIB() { fake = 1; atr.clear(); tree.clear(); }
};
struct AIB2D {
int n;
AIB tree[nmax];
void init(int n_) {
n = n_ + 1;
}
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, tmp;
cin >> s;
s = "#" + s;
for(int i = 1; i <= n; i++) last[i] = 1;
tmp = s;
for(int i = 2; i <= q + 1; i++) {
string act;
cin >> act;
if(act == "toggle") {
int x;
cin >> x;
upds[x].emplace_back(last[x], i - 1, s[x] - '0');
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);
}
}
for(int i = 1; i <= n; i++) {
upds[i].emplace_back(last[i], q + 1, s[i] - '0');
}
Beats::init(q + 1);
for(int i = 1; i <= n; i++) {
for(auto [u, d, type] : upds[i]) {
if(type == 1) continue;
Beats::set(u, d, i);
}
}
Beats::set(1, q + 1, n + 1);
for(auto &[l, r, u, d] : squares) {
++l, --r;
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 < 2; 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.
--
*/
