#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + 10;
const int MOD = 998244353;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
long long bm(long long b, long long p) {
if(p==0) return 1 % MOD;
long long r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
long long inv(long long b) {
return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) {
long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); }
int fastlog(int x) {
return (x == 0 ? -1 : 32 - __builtin_clz(x) - 1);
}
void gay(int i) { cout << "Case #" << i << ": "; }
char ss[MAXN]; int n, q, t;
struct query {
int x, y, v;
bool is_qry;
int ans;
int id;
};
query ended[5 * MAXN], cnt[5 * MAXN], sum[5 * MAXN];
int e = 0, c = 0, s = 0;
int l[MAXN], r[MAXN];
set<pair<int, int> > all_segments;
unordered_map<int, int> simple_ended[MAXN], simple_cnt[MAXN], simple_sum[MAXN];
int global_id;
void insert_segment(int x, int y) {
l[y] = x;
r[x] = y;
all_segments.insert({y, x});
cnt[c++] = {x, y, 1, 0, 0, ++global_id};
sum[s++] = {x, y, t, 0, 0, ++global_id};
simple_cnt[x][y] += 1;
simple_sum[x][y] += t;
}
void delete_segment(int x, int y) {
all_segments.erase({y, x});
simple_ended[x][y] += t - simple_sum[x][y];
ended[e++] = {x, y, t - simple_sum[x][y], 0, 0, ++global_id};
cnt[c++] = {x, y, -simple_cnt[x][y], 0, 0, ++global_id};
simple_cnt[x].erase(y);
sum[s++] = {x, y, -simple_sum[x][y], 0, 0, ++global_id};
simple_sum[x].erase(y);
r[x] = l[y] = -1;
}
bool cmp2(query a, query b) {
return a.id < b.id;
}
int bit[MAXN];
void add(int x, int v) {
for(;x<MAXN;x+=x&-x) {
bit[x] += v;
}
}
int bit_sum(int x) {
int sss = 0;
for(;x;x-=x&-x) sss += bit[x];
return sss;
}
int ct3 = 0;
int pt[MAXN];
void moshang_huakai(int array_id, int lb, int rb) {
++ct3;
if(lb == rb) return;
int mid = (lb + rb) >> 1;
moshang_huakai(array_id, lb, mid);
moshang_huakai(array_id, mid + 1, rb);
pair<int, int> ll[mid - lb + 1], rr[rb - mid];
for(int i=lb; i<=mid; i++) {
if(array_id == 0) ll[i - lb] = {ended[i].x, i};
else if(array_id == 1) ll[i - lb] = {cnt[i].x, i};
else ll[i - lb] = {sum[i].x, i};
}
for(int i=mid+1; i<=rb; i++) {
if(array_id == 0) rr[i - (mid + 1)] = {ended[i].x, i};
else if(array_id == 1) rr[i - (mid + 1)] = {cnt[i].x, i};
else rr[i - (mid + 1)] = {sum[i].x, i};
}
sort(ll, ll + mid - lb + 1);
sort(rr, rr + rb - mid);
int nxt = ll[0].second;
int ti = 0;
int upd[rb - mid + 2];
int newidx = 0;
for(int j=mid+1; j<=rb; j++) {
int i = rr[j - (mid + 1)].second;
if(ti < mid - lb + 1) {
int xval, curx;
if(array_id == 0) xval = ended[nxt].x, curx = ended[i].x;
else if(array_id == 1) xval = cnt[nxt].x, curx = cnt[i].x;
else xval = sum[nxt].x, curx = sum[i].x;
while(ti < mid - lb + 1 && xval <= curx) {
int yval, cury, ysum;
if(array_id == 0) yval = ended[nxt].y, cury = ended[i].y, ysum = ended[nxt].v;
else if(array_id == 1) yval = cnt[nxt].y, cury = cnt[i].y, ysum = cnt[nxt].v;
else yval = sum[nxt].y, cury = sum[i].y, ysum = sum[nxt].v;
add(yval + 1, ysum);
pt[yval + 1] += ysum;
//cout << "hi " << yval << " += " << ysum << ", " << array_id << "\n";
upd[newidx++] = yval + 1;
ti++;
if(ti >= mid - lb + 1) break;
nxt = ll[ti].second;
if(array_id == 0) xval = ended[nxt].x;
else if(array_id == 1) xval = cnt[nxt].x;
else xval = sum[nxt].x;
}
}
int cury;
if(array_id == 0) cury = ended[i].y;
else if(array_id == 1) cury = cnt[i].y;
else cury = sum[i].y;
if(array_id == 0) ended[i].ans += bit_sum(cury + 1);
else if(array_id == 1) cnt[i].ans += bit_sum(cury + 1);
else sum[i].ans += bit_sum(cury + 1);
}
for(int i=0; i<newidx; i++) {
int x = upd[i];
add(x, -pt[x]);
pt[x] = 0;
}
}
void solve(int tc) {
t = 0;
//n = 300000, q = 300000;
cin >> n >> q;
for(int i=1; i<=n; i++) {
//ss[i] = char(rnd(0, 1) + '0');
cin >> ss[i];
}
for(int i=0; i<=n+1; i++) l[i] = r[i] = -1;
for(int i=1; i<=n; i++) {
if(ss[i] == '1') {
int j = i;
while(j + 1 <= n && ss[j+1] == '1') ++j;
insert_segment(i, j);
i = j + 1;
}
}
all_segments.insert({1e7, 1e7});
vector<int> Times;
while(q--) {
++t;
string str;
//str = (rnd(0, 1) ? "toggle" : "q");
cin >> str;
if(str == "toggle") {
int i;
//i = rnd(1, n);
cin >> i;
ss[i] = (ss[i] == '1' ? '0' : '1');
if(ss[i] == '1') {
if(l[i-1] != -1) {
int sto = l[i-1];
delete_segment(sto, i-1);
insert_segment(sto, i);
}
else {
insert_segment(i, i);
}
if(r[i+1] != -1) {
int sto = r[i+1];
int sto2 = l[i];
delete_segment(l[i], i);
delete_segment(i+1, sto);
insert_segment(sto2, sto);
}
}
else {
auto it = all_segments.lower_bound({i, 0});
pair<int, int> seg = *it;
if(seg.first != 1e7 && seg.second <= i && i <= seg.first) {
int ff = seg.second, ss = seg.first;
delete_segment(ff, ss);
if(ff < i) insert_segment(ff, i - 1);
if(i < ss) insert_segment(i + 1, ss);
}
}
}
else {
int a, b;
cin >> a >> b;
/*
while(1) {
a = rnd(1, n + 1);
b = rnd(1, n + 1);
if(a < b) break;
}
*/
b--;
ended[e++] = {a, n, 0, 1, 0, ++global_id};
ended[e++] = {a, b - 1, 0, 1, 0, ++global_id};
cnt[c++] = {a, n, 0, 1, 0, ++global_id};
cnt[c++] = {a, b - 1, 0, 1, 0, ++global_id};
sum[s++] = {a, n, 0, 1, 0, ++global_id};
sum[s++] = {a, b - 1, 0, 1, 0, ++global_id};
//Ans = (if tcnt = 0: ended, else ended + t * tcnt - tsum)
Times.push_back(t);
}
}
moshang_huakai(0, 0, e - 1);
moshang_huakai(1, 0, c - 1);
moshang_huakai(2, 0, s - 1);
vector<int> ended_ans, cnt_ans, sum_ans;
for(int i=0; i<e; i++) {
if(ended[i].is_qry == 1) {
ended_ans.push_back(ended[i].ans);
}
}
for(int i=0; i<c; i++) {
if(cnt[i].is_qry == 1) {
cnt_ans.push_back(cnt[i].ans);
}
}
for(int i=0; i<s; i++) {
if(sum[i].is_qry == 1) {
sum_ans.push_back(sum[i].ans);
}
}
assert(ended_ans.size() == cnt_ans.size() && cnt_ans.size() == sum_ans.size());
int sz = ended_ans.size();
for(int i=0; i<sz; i+=2) {
int ans = ended_ans[i] - ended_ans[i + 1];
int tcnt = cnt_ans[i] - cnt_ans[i + 1];
int tsum = sum_ans[i] - sum_ans[i + 1];
if(tcnt == 0) cout << ans << '\n';
else cout << ans + Times[i >> 1] * tcnt - tsum << '\n';
}
}
/*
5 1 11011
query 1 2
5 7 11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
int32_t main() {
precomp();
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
