#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 3e5 + 100;
ve<ve<int>> q[3]; ve<ve<int>> f[3]; int nn;
inline void pupd(int id, int x, int y) { x += 2; for (; x < nn; x += x & -x) q[id][x].pb(y); }
inline void pget(int id, int x, int y) { x += 2; for (; x; x -= x & -x) q[id][x].pb(y); }
inline void psum(int id, int lx, int ry) { pget(id, lx, nn - 5); pget(id, lx, ry - 1); }
inline void prep(int id) {
for (int i = 0; i < nn; ++i) {
sort(all(q[id][i]));
q[id][i].erase(unique(all(q[id][i])), q[id][i].end());
f[id][i].resize(sz(q[id][i]) + 10);
}
}
inline void upd(int id, int x, int y, int d) { x += 2;
for (; x < nn; x += x & -x) {
int i = lower_bound(all(q[id][x]), y) - q[id][x].begin() + 2;
for (; i < sz(f[id][x]); i += i & -i) f[id][x][i] += d;
}
}
inline int get(int id, int x, int y) {
if (y < 0) return 0;
x += 2; int ans = 0;
for (; x; x -= x & -x) {
int i = lower_bound(all(q[id][x]), y) - q[id][x].begin() + 2;
for (; i; i -= i & -i) ans += f[id][x][i];
} return ans;
}
inline int sum(int id, int lx, int ry) { return get(id, lx, nn - 5) - get(id, lx, ry - 1); }
inline void begin(int n) {
nn = n + 10;
for (int i : {0, 1, 2}) {
f[i].resize(nn);
q[i].resize(nn);
}
}
inline void solve() {
int n, q;
cin >> n >> q;
string s; cin >> s;
begin(n);
string ini = s;
map<int,array<int,3>> mp; int ls = -1;
for (int i = n - 1; ~i; --i) {
if (s[i] == '1' && ls == -1) ls = i;
else if (s[i] == '0') {
if (i + 1 < n && s[i + 1] == '1') {
mp[i + 1] = {ls, 0, iinf};
} ls = -1;
}
}
if (s[0] == '1') mp[0] = {ls, 0, iinf};
auto Padd_seg = [&](int lt, int rt, int l, int r) {
pupd(0, l, r);
if (rt == iinf) pupd(1, l, r);
else pupd(2, l, r);
};
auto add_seg = [&](int lt, int rt, int l, int r, bool fl = 0) {
if (fl) upd(0, l, r, -lt);
if (rt == iinf) upd(1, l, r, +1);
else upd(2, l, r, +(rt + 1));
};
auto del_seg = [&](int lt, int rt, int l, int r, bool fl = 0) {
if (fl) upd(0, l, r, +lt);
if (rt == iinf) upd(1, l, r, -1);
else upd(2, l, r, -(rt + 1));
};
for (auto &[l, __] : mp) {
auto &[r, lt, rt] = __;
Padd_seg(lt, rt, l, r);
}
auto Pupd = [&](int pos, int curtime) {
if (s[pos] == '0') {
pii add = {pos, pos};
auto it = mp.upper_bound(pos);
if (it != mp.end()) {
auto [r, lt, rt] = it->se;
if (it->fi == pos + 1) {
add = {add.fi, r};
Padd_seg(lt, curtime - 1, it->fi, r);
mp.erase(it);
}
}
it = mp.upper_bound(pos);
if (it != mp.begin()) {
--it;
auto [r, lt, rt] = it->se;
if (r == pos - 1) {
add = {it->fi, add.se};
Padd_seg(lt, curtime - 1, it->fi, r);
mp.erase(it);
}
}
Padd_seg(curtime, iinf, add.fi, add.se);
mp[add.fi] = {add.se, curtime, iinf};
}
else {
auto it = mp.upper_bound(pos); --it;
int l = it->fi; auto [r, lt, rt] = it->se;
Padd_seg(lt, curtime - 1, l, r);
mp.erase(it);
if (l != r) {
if (pos == l) Padd_seg(curtime, iinf, l + 1, r), mp[l + 1] = {r, curtime, iinf};
else if (pos == r) Padd_seg(curtime, iinf, l, r - 1), mp[l] = {r - 1, curtime, iinf};
else {
Padd_seg(curtime, iinf, l, pos - 1);
Padd_seg(curtime, iinf, pos + 1, r);
mp[l] = {pos - 1, curtime, iinf};
mp[pos + 1] = {r, curtime, iinf};
}
}
}
s[pos] = (s[pos] == '0' ? '1' : '0');
};
auto upd = [&](int pos, int curtime) {
if (s[pos] == '0') {
pii add = {pos, pos};
auto it = mp.upper_bound(pos);
if (it != mp.end()) {
auto [r, lt, rt] = it->se;
if (it->fi == pos + 1) {
add = {add.fi, r};
del_seg(lt, rt, it->fi, r);
add_seg(lt, curtime - 1, it->fi, r);
mp.erase(it);
}
}
it = mp.upper_bound(pos);
if (it != mp.begin()) {
--it;
auto [r, lt, rt] = it->se;
if (r == pos - 1) {
add = {it->fi, add.se};
del_seg(lt, rt, it->fi, r);
add_seg(lt, curtime - 1, it->fi, r);
mp.erase(it);
}
}
add_seg(curtime, iinf, add.fi, add.se, 1);
mp[add.fi] = {add.se, curtime, iinf};
}
else {
auto it = mp.upper_bound(pos); --it;
int l = it->fi; auto [r, lt, rt] = it->se;
del_seg(lt, rt, l, r);
add_seg(lt, curtime - 1, l, r);
mp.erase(it);
if (l != r) {
if (pos == l) add_seg(curtime, iinf, l + 1, r, 1), mp[l + 1] = {r, curtime, iinf};
else if (pos == r) add_seg(curtime, iinf, l, r - 1, 1), mp[l] = {r - 1, curtime, iinf};
else {
add_seg(curtime, iinf, l, pos - 1, 1);
add_seg(curtime, iinf, pos + 1, r, 1);
mp[l] = {pos - 1, curtime, iinf};
mp[pos + 1] = {r, curtime, iinf};
}
}
}
s[pos] = (s[pos] == '0' ? '1' : '0');
};
int ttm = 0;
ve<array<int,3>> que(q);
for (int i = 0; i < q; ++i) { ttm++;
string e; cin >> e;
que[i][0] = (e == "toggle" ? 0 : 1);
if (e == "toggle") {
int pos;
cin >> pos, --pos;
Pupd(pos, ttm++);
que[i][1] = pos;
que[i][2] = -1;
}
else {
int l, r;
cin >> l >> r, --l, ----r;
que[i][1] = l, que[i][2] = r;
psum(0, l, r);
psum(1, l, r);
psum(2, l, r);
}
}
prep(0), prep(1), prep(2);
s = ini; mp.clear(); ls = -1;
for (int i = n - 1; ~i; --i) {
if (s[i] == '1' && ls == -1) ls = i;
else if (s[i] == '0') {
if (i + 1 < n && s[i + 1] == '1') {
mp[i + 1] = {ls, 0, iinf};
} ls = -1;
}
}
if (s[0] == '1') mp[0] = {ls, 0, iinf};
for (auto &[l, __] : mp) add_seg(0, iinf, l, __[0], 1);
int tm = 0;
for (auto &[e, l, r] : que) { ++tm;
if (!e) upd(l, tm);
else {
int ans = 0;
ans += sum(2, l, r);
ans += sum(0, l, r);
ans += tm * sum(1, l, r);
cout << ans << '\n';
}
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
/**
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 5
query 1 6
*/
