// "I assure you that you guys won't make it to the top 4"
// - Tzaph, 21 December 2021
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
#define ld long double
#define si short int
#define i8 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define psi pair<si, si>
#define pi8 pair<i8, i8>
#define pq priority_queue
#define fi first
#define se second
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}
const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
const int maxN = 3e5 + 5;
struct FenwickTree {
ll sz;
vector<ll> BIT;
FenwickTree(ll _sz) {
sz = _sz;
BIT.assign(_sz+1, 0);
}
void update(ll idx, ll val) {
for (; idx <= sz; idx += (idx & -idx)) {
BIT[idx] += val;
}
}
ll sum(ll idx) {
ll ret = 0;
idx = min(idx, sz);
for (; idx > 0; idx -= (idx & -idx)) {
ret += BIT[idx];
}
return ret;
}
ll query(ll l, ll r) {
return sum(r) - sum(l-1);
}
};
struct FenwickTree2D {
ll sz;
vector<FenwickTree> inner;
vector<vector<ll>> pos;
FenwickTree2D(ll _sz) {
sz = _sz;
pos.assign(_sz + 1, vector<ll>(0));
}
void addPos(ll d1, ll d2) {
for (; d1 <= sz; d1 += (d1 & -d1)) {
pos[d1].push_back(d2);
}
}
void build() {
for (ll i = 0; i <= sz; i++) {
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
inner.push_back(FenwickTree(pos[i].size()));
}
}
void update(ll d1, ll d2, ll val) {
for (; d1 <= sz; d1 += (d1 & -d1)) {
ll d2_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2) - pos[d1].begin() + 1;
//cout << d1 << ' ' << d2 << ' ' << d2_compressed << '\n';
inner[d1].update(d2_compressed, val);
}
}
ll sum(ll d1, ll d2l, ll d2r) {
ll ret = 0;
for (; d1 > 0; d1 -= (d1 & -d1)) {
ll d2l_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2l) - pos[d1].begin() + 1;
ll d2r_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2r) - pos[d1].begin() + 1;
//cout << d1 << ' ' << d2l_compressed << ' ' << d2r_compressed << '\n';
ret += inner[d1].query(d2l_compressed, d2r_compressed);
}
return ret;
}
ll query(ll d1l, ll d1r, ll d2l, ll d2r) {
//cout << sum(d1r, d2l, d2r) << ' ' << sum(d1l-1, d2l, d2r) << '\n';
return sum(d1r, d2l, d2r) - sum(d1l-1, d2l, d2r);
}
void printPos() {
for (ll i = 1; i <= sz; i++) {
cout << i << ": ";
for (auto j : pos[i]) {cout << j << " ";}
cout << '\n';
}
}
void print() {
for (ll i = 1; i <= sz; i++) {
cout << i << ": ";
for (auto j : pos[i]) {
cout << "{" << j << ": " << query(i, i, j, j) << "} ";
}
cout << '\n';
}
}
};
struct Operation {
bool typ; // 0 = update, 1 = query
ll x1, y1, x2, y2, t;
pll val;
Operation(ll _x1, ll _y1, pll _val) {
typ = 0;
x1 = _x1, y1 = _y1, val = _val;
}
Operation(ll _x1, ll _y1, ll _x2, ll _y2, ll _t) {
typ = 1;
x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2, t = _t;
}
};
int n, q;
bool lamps[maxN];
set<pll> segments;
vector<Operation> op;
int main() {
scanf("%d %d", &n, &q);
char c;
for (int i = 1; i <= n; i++) {
scanf(" %c", &c);
lamps[i] = (c == '1');
}
FenwickTree2D values = FenwickTree2D(n);
FenwickTree2D toggled = FenwickTree2D(n);
// NOTE: because we need <= operator in lower_bound,
// all set elements are negative
for (int start = -1, i = 1; i <= n+1; i++) {
if (lamps[i]) {
if (start == -1) {start = i;}
} else {
if (start != -1) {
segments.insert({-start, -(i-1)});
values.addPos(start, i-1);
toggled.addPos(start, i-1);
op.push_back(Operation(start, i-1, {q, 1}));
start = -1;
}
}
}
char typ[10];
for (int a, b, i = 1; i <= q; i++) {
scanf(" %s", typ);
if (typ[0] == 't') {
scanf("%d", &a);
if (lamps[a]) {
// toggle the lamp off
// remove segment of current lamp
auto cseg_it = segments.lower_bound({-a, -iINF});
pll cseg = *cseg_it;
//cout << "cseg " << cseg.fi << ' ' << cseg.se << '\n';
segments.erase(cseg);
values.addPos(-cseg.fi, -cseg.se);
toggled.addPos(-cseg.fi, -cseg.se);
op.push_back(Operation(-cseg.fi, -cseg.se, {-(q-i), -1}));
// insert new segments (except if it's of length 0)
// left segment
if (a != -cseg.fi) {
segments.insert({cseg.fi, -(a-1)});
values.addPos(-cseg.fi, a-1);
toggled.addPos(-cseg.fi, a-1);
op.push_back(Operation(-cseg.fi, a-1, {q-i, 1}));
}
// right segment
if (a != -cseg.se) {
segments.insert({-(a+1), cseg.se});
values.addPos(a+1, -cseg.se);
toggled.addPos(a+1, -cseg.se);
op.push_back(Operation(a+1, -cseg.se, {q-i, 1}));
}
} else {
// toggle the lamp on
pll newseg = {-a, -a};
// check if lamps next to it are on
// left
if (lamps[a-1]) {
auto lseg_it = segments.lower_bound({-(a-1), -iINF});
pll lseg = *lseg_it;
newseg.fi = lseg.fi;
segments.erase(lseg);
values.addPos(-lseg.fi, -lseg.se);
toggled.addPos(-lseg.fi, -lseg.se);
op.push_back(Operation(-lseg.fi, -lseg.se, {-(q-i), -1}));
}
// right
if (lamps[a+1]) {
auto rseg_it = segments.lower_bound({-(a+1), -iINF});
pll rseg = *rseg_it;
newseg.se = rseg.se;
segments.erase(rseg);
values.addPos(-rseg.fi, -rseg.se);
toggled.addPos(-rseg.fi, -rseg.se);
op.push_back(Operation(-rseg.fi, -rseg.se, {-(q-i), -1}));
}
// insert new segment
segments.insert(newseg);
values.addPos(-newseg.fi, -newseg.se);
toggled.addPos(-newseg.fi, -newseg.se);
op.push_back(Operation(-newseg.fi, -newseg.se, {q-i, 1}));
}
lamps[a] = !lamps[a];
} else {
scanf("%d %d", &a, &b);
op.push_back(Operation(1, b-1, a, n, i));
}
//for (auto i : segments) {cout << "{" << i.fi << ", " << i.se << "} ";}
//cout << '\n';
//D.print();
//cout << '\n';
}
values.build();
toggled.build();
//values.printPos();
//toggled.printPos();
for (auto O : op) {
if (O.typ == 0) {
//printf("Update %lld %lld with %lld %lld\n", O.x1, O.y1, O.val.fi, O.val.se);
values.update(O.x1, O.y1, O.val.fi);
toggled.update(O.x1, O.y1, O.val.se);
//values.print();
//toggled.print();
} else {
//printf("Query (%lld %lld) to (%lld %lld) at time %lld\n", O.x1, O.y1, O.x2, O.y2, O.t);
ll v = values.query(O.x1, O.x2, O.y1, O.y2);
ll t = toggled.query(O.x1, O.x2, O.y1, O.y2);
//printf("%lld %lld\n", v, t);
ll fin = v - (1ll * t * (q-O.t));
printf("%lld\n", fin);
}
}
}
