#include <iostream>
#include <vector>
using namespace std;
struct node {
int value = 0;
node * right, * left;
int l, r;
int unPushed = 0;
node(int l, int r) : left(nullptr), right(nullptr), l(l), r(r) { }
node * clone() {
node * ans = new node(l, r);
ans -> right = right;
ans -> left = left;
ans -> value = value;
ans -> unPushed = unPushed;
return ans;
}
};
vector<node *> v;
int sum(node * left, node * right) {
int ans = 0;
if(left != nullptr) ans += left -> value;
if(right != nullptr) ans += right -> value;
return ans;
}
void push(node *(&k)) {
k -> unPushed %= 2;
if (k -> unPushed) {
int center = (k -> l + k -> r) / 2;
if (k -> left == nullptr) k -> left = new node(k -> l, center);
else k -> left = k -> left -> clone();
if (k -> right == nullptr) k -> right = new node(center + 1, k -> r);
else k -> right = k -> right -> clone();
++k -> left -> unPushed;
++k -> right -> unPushed;
k -> left -> value = (center - k -> l + 1) - k -> left -> value;
k -> right -> value = (k -> r - center) - k -> right -> value;
k -> unPushed = 0;
}
}
void updateSegment(node *(&k), int left, int right, int l, int r) {
if(k == nullptr) k = new node(left, right);
else k = k -> clone();
if(l > r) return;
if(l == left && r == right) {
++k -> unPushed;
k -> value = (r - l + 1) - k -> value;
return;
}
int center = (left + right) / 2;
push(k);
updateSegment(k -> left, left, center, l, min(r, center));
updateSegment(k -> right, center + 1, right, max(l, center + 1), r);
push(k -> left);
push(k -> right);
k -> value = sum(k -> left, k -> right);
}
void update(node *&k, int left, int right, int pos, int a) {
if (k == nullptr) k = new node(left, right);
else k = k -> clone();
if (left == right) {
k -> value = a;
return;
}
int center = (left + right) / 2;
push(k);
if(pos <= center) {
update(k -> left, left, center, pos, a);
push(k -> left);
}
else {
update(k -> right, center + 1, right, pos, a);
push(k -> right);
}
k -> value = sum (k -> left, k -> right);
}
int query(node *k, int left, int right, int l, int r) {
if (l > r) return 0;
if(k == nullptr) return 0;
if(left == l && r == right) return k -> value;
int center = (left + right) / 2;
push(k);
return query(k -> left, left, center, l, min(center, r)) + query(k -> right, center + 1, right, max(l, center + 1), r);
}
int main() {
int n, m, type, pos, l, r;
scanf("%d %d", &n, &m);
v.push_back(new node(1, n));
for(int i = 1; i <= m; i++) {
scanf("%d", &type);
if(type <= 2) {
scanf("%d", &pos);
type = 2 - type;
v.push_back(v.back() -> clone());
int k = query(v.back(), 1, n, pos, pos);
if(k != type) updateSegment(v.back(), 1, n, pos, pos);
}
else if(type == 3) {
scanf("%d %d", &l, &r);
v.push_back(v.back() -> clone());
updateSegment(v.back(), 1, n, l, r);
}
else if(type == 4) {
scanf("%d", &pos);
v.push_back(v[pos] -> clone());
}
else if(type == 5) {
scanf("%d %d", &l, &r);
v.push_back(v.back() -> clone());
printf("%d\n", query(v.back(), 1, n, l, r));
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IG5vZGUgewogICAgaW50IHZhbHVlID0gMDsKICAgIG5vZGUgKiByaWdodCwgKiBsZWZ0OwogICAgaW50IGwsIHI7CiAgICBpbnQgdW5QdXNoZWQgPSAwOwogICAgbm9kZShpbnQgbCwgaW50IHIpIDogbGVmdChudWxscHRyKSwgcmlnaHQobnVsbHB0ciksIGwobCksIHIocikgeyB9CiAgICBub2RlICogY2xvbmUoKSB7CiAgICAgICAgbm9kZSAqIGFucyA9IG5ldyBub2RlKGwsIHIpOwogICAgICAgIGFucyAtPiByaWdodCA9IHJpZ2h0OwogICAgICAgIGFucyAtPiBsZWZ0ID0gbGVmdDsKICAgICAgICBhbnMgLT4gdmFsdWUgPSB2YWx1ZTsKICAgICAgICBhbnMgLT4gdW5QdXNoZWQgPSB1blB1c2hlZDsKICAgICAgICByZXR1cm4gYW5zOwogICAgfQp9Owp2ZWN0b3I8bm9kZSAqPiB2OwppbnQgc3VtKG5vZGUgKiBsZWZ0LCBub2RlICogcmlnaHQpIHsKICAgIGludCBhbnMgPSAwOwogICAgaWYobGVmdCAhPSBudWxscHRyKSBhbnMgKz0gbGVmdCAtPiB2YWx1ZTsKICAgIGlmKHJpZ2h0ICE9IG51bGxwdHIpIGFucyArPSByaWdodCAtPiB2YWx1ZTsKICAgIHJldHVybiBhbnM7Cn0Kdm9pZCBwdXNoKG5vZGUgKigmaykpIHsKICAgIGsgLT4gdW5QdXNoZWQgJT0gMjsKICAgIGlmIChrIC0+IHVuUHVzaGVkKSB7CiAgICAgICAgaW50IGNlbnRlciA9IChrIC0+IGwgKyBrIC0+IHIpIC8gMjsKICAgICAgICBpZiAoayAtPiBsZWZ0ID09IG51bGxwdHIpIGsgLT4gbGVmdCA9IG5ldyBub2RlKGsgLT4gbCwgY2VudGVyKTsKICAgICAgICBlbHNlIGsgLT4gbGVmdCA9IGsgLT4gbGVmdCAtPiBjbG9uZSgpOwogICAgICAgIGlmIChrIC0+IHJpZ2h0ID09IG51bGxwdHIpIGsgLT4gcmlnaHQgPSBuZXcgbm9kZShjZW50ZXIgKyAxLCBrIC0+IHIpOwogICAgICAgIGVsc2UgayAtPiByaWdodCA9IGsgLT4gcmlnaHQgLT4gY2xvbmUoKTsKICAgICAgICArK2sgLT4gbGVmdCAtPiB1blB1c2hlZDsKICAgICAgICArK2sgLT4gcmlnaHQgLT4gdW5QdXNoZWQ7CiAgICAgICAgayAtPiBsZWZ0IC0+IHZhbHVlID0gKGNlbnRlciAtIGsgLT4gbCArIDEpIC0gayAtPiBsZWZ0IC0+IHZhbHVlOwogICAgICAgIGsgLT4gcmlnaHQgLT4gdmFsdWUgPSAoayAtPiByIC0gY2VudGVyKSAtIGsgLT4gcmlnaHQgLT4gdmFsdWU7CiAgICAgICAgayAtPiB1blB1c2hlZCA9IDA7CiAgICB9CiAgIAp9CnZvaWQgdXBkYXRlU2VnbWVudChub2RlICooJmspLCBpbnQgbGVmdCwgaW50IHJpZ2h0LCBpbnQgbCwgaW50IHIpIHsKICAgIGlmKGsgPT0gbnVsbHB0cikgayA9IG5ldyBub2RlKGxlZnQsIHJpZ2h0KTsKICAgIGVsc2UgayA9IGsgLT4gY2xvbmUoKTsKICAgIGlmKGwgPiByKSByZXR1cm47CiAgICBpZihsID09IGxlZnQgJiYgciA9PSByaWdodCkgewogICAgICAgICsrayAtPiB1blB1c2hlZDsKICAgICAgICBrIC0+IHZhbHVlID0gKHIgLSBsICsgMSkgLSBrIC0+IHZhbHVlOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBjZW50ZXIgPSAobGVmdCArIHJpZ2h0KSAvIDI7CiAgICBwdXNoKGspOwogICAgdXBkYXRlU2VnbWVudChrIC0+IGxlZnQsIGxlZnQsIGNlbnRlciwgbCwgbWluKHIsIGNlbnRlcikpOwogICAgdXBkYXRlU2VnbWVudChrIC0+IHJpZ2h0LCBjZW50ZXIgKyAxLCByaWdodCwgbWF4KGwsIGNlbnRlciArIDEpLCByKTsKICAgIHB1c2goayAtPiBsZWZ0KTsKICAgIHB1c2goayAtPiByaWdodCk7CiAgICBrIC0+IHZhbHVlID0gc3VtKGsgLT4gbGVmdCwgayAtPiByaWdodCk7Cn0Kdm9pZCB1cGRhdGUobm9kZSAqJmssIGludCBsZWZ0LCBpbnQgcmlnaHQsIGludCBwb3MsIGludCBhKSB7CiAgICBpZiAoayA9PSBudWxscHRyKSBrID0gbmV3IG5vZGUobGVmdCwgcmlnaHQpOwogICAgZWxzZSBrID0gayAtPiBjbG9uZSgpOwogICAgaWYgKGxlZnQgPT0gcmlnaHQpIHsKICAgICAgICBrIC0+IHZhbHVlID0gYTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgY2VudGVyID0gKGxlZnQgKyByaWdodCkgLyAyOwogICAgcHVzaChrKTsKICAgIGlmKHBvcyA8PSBjZW50ZXIpIHsKICAgICAgICB1cGRhdGUoayAtPiBsZWZ0LCBsZWZ0LCBjZW50ZXIsIHBvcywgYSk7CiAgICAgICAgcHVzaChrIC0+IGxlZnQpOwogICAgfQogICAgZWxzZSB7CiAgICAgICAgdXBkYXRlKGsgLT4gcmlnaHQsIGNlbnRlciArIDEsIHJpZ2h0LCBwb3MsIGEpOwogICAgICAgIHB1c2goayAtPiByaWdodCk7CiAgICB9CiAgICBrIC0+IHZhbHVlID0gc3VtIChrIC0+IGxlZnQsIGsgLT4gcmlnaHQpOwp9CmludCBxdWVyeShub2RlICprLCBpbnQgbGVmdCwgaW50IHJpZ2h0LCBpbnQgbCwgaW50IHIpIHsKICAgIGlmIChsID4gcikgcmV0dXJuIDA7CiAgICBpZihrID09IG51bGxwdHIpIHJldHVybiAwOwogICAgaWYobGVmdCA9PSBsICYmIHIgPT0gcmlnaHQpIHJldHVybiBrIC0+IHZhbHVlOwogICAgaW50IGNlbnRlciA9IChsZWZ0ICsgcmlnaHQpIC8gMjsKICAgIHB1c2goayk7CiAgICByZXR1cm4gcXVlcnkoayAtPiBsZWZ0LCBsZWZ0LCBjZW50ZXIsIGwsIG1pbihjZW50ZXIsIHIpKSArIHF1ZXJ5KGsgLT4gcmlnaHQsIGNlbnRlciArIDEsIHJpZ2h0LCBtYXgobCwgY2VudGVyICsgMSksIHIpOwp9CgppbnQgbWFpbigpIHsKCWludCBuLCBtLCB0eXBlLCBwb3MsIGwsIHI7CglzY2FuZigiJWQgJWQiLCAmbiwgJm0pOwogICAgdi5wdXNoX2JhY2sobmV3IG5vZGUoMSwgbikpOwogICAgZm9yKGludCBpID0gMTsgaSA8PSBtOyBpKyspIHsKICAgICAgICBzY2FuZigiJWQiLCAmdHlwZSk7CiAgICAgICAgaWYodHlwZSA8PSAyKSB7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZwb3MpOwogICAgICAgICAgICB0eXBlID0gMiAtIHR5cGU7CiAgICAgICAgICAgIHYucHVzaF9iYWNrKHYuYmFjaygpIC0+IGNsb25lKCkpOwogICAgICAgICAgICBpbnQgayA9IHF1ZXJ5KHYuYmFjaygpLCAxLCBuLCBwb3MsIHBvcyk7CiAgICAgICAgICAgIGlmKGsgIT0gdHlwZSkgdXBkYXRlU2VnbWVudCh2LmJhY2soKSwgMSwgbiwgcG9zLCBwb3MpOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKHR5cGUgPT0gMykgewogICAgICAgICAgICBzY2FuZigiJWQgJWQiLCAmbCwgJnIpOwogICAgICAgICAgICB2LnB1c2hfYmFjayh2LmJhY2soKSAtPiBjbG9uZSgpKTsKICAgICAgICAgICAgdXBkYXRlU2VnbWVudCh2LmJhY2soKSwgMSwgbiwgbCwgcik7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYodHlwZSA9PSA0KSB7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZwb3MpOwogICAgICAgICAgICB2LnB1c2hfYmFjayh2W3Bvc10gLT4gY2xvbmUoKSk7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYodHlwZSA9PSA1KSB7CiAgICAgICAgICAgIHNjYW5mKCIlZCAlZCIsICZsLCAmcik7CiAgICAgICAgICAgIHYucHVzaF9iYWNrKHYuYmFjaygpIC0+IGNsb25lKCkpOwogICAgICAgICAgICBwcmludGYoIiVkXG4iLCBxdWVyeSh2LmJhY2soKSwgMSwgbiwgbCwgcikpOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9