// not enough memory for this, but oh well idfc its probably the most efficient solution time-wise
// i dont like batching so i will do this instead
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <random>
std::mt19937 rng(53);
template<typename Type>
class FenwickTree {
private:
std::vector<Type> bit;
public:
FenwickTree(int size = 0, Type val = 0) {
assign(size,val);
}
void assign(int size = 0, Type val = 0) {
bit.assign(size,0);
if (size&&val) {
for (int i = 1; i < size; i++) {
bit[i] += val;
if (i+(i&-i)<bit.size()) {
bit[i+(i&-i)] += bit[i];
}
}
}
}
void add(int poz, Type val) {
while (poz<bit.size()) {
bit[poz] += val;
poz += poz&-poz;
}
}
Type query(int poz) {
Type ret = 0;
while (poz>0) {
ret += bit[poz];
poz ^= poz&-poz;
}
return ret;
}
Type query(int l, int r) {
return query(r) - query(l-1);
}
int binary_lifting(Type val) {
int ret = 0;
for (int step = 1<<18; step; step >>= 1) {
if (ret+step<bit.size()&&val-bit[ret+step]>0) {
val -= bit[ret+step];
ret += step;
}
}
return ++ret;
}
};
namespace Treap {
struct Node {
int val;
int size;
int prio;
Node* l;
Node* r;
Node(int val = 0):
val(val), size(1), prio(rng()), l(nullptr), r(nullptr) {}
~Node() {
if (l) delete l;
if (r) delete r;
}
};
Node* _aux_merge = nullptr;
Node* _aux_split_l = nullptr;
Node* _aux_split_r = nullptr;
inline int NodeGetSize(Node* node) {
if (!node) return 0;
return node->size;
}
inline void NodeUpdateSize(Node* node) {
if (!node) return;
node->size = 1 + NodeGetSize(node->l) + NodeGetSize(node->r);
}
void SplitDriver(Node* node, int key) {
if (!node) {
_aux_split_l = _aux_split_r = nullptr;
return;
}
if (key<=NodeGetSize(node->l)) {
SplitDriver(node->l,key);
node->l = _aux_split_r;
_aux_split_r = node;
NodeUpdateSize(node);
}
else {
SplitDriver(node->r,key-NodeGetSize(node->l)-1);
node->r = _aux_split_l;
_aux_split_l = node;
NodeUpdateSize(node);
}
}
std::pair<Node*, Node*> Split(Node* node, int key) {
SplitDriver(node,key);
return {_aux_split_l, _aux_split_r};
}
void MergeDriver(Node* a, Node* b) {
if (!a) {
_aux_merge = b;
return;
}
if (!b) {
_aux_merge = a;
return;
}
if (a->prio > b->prio) {
MergeDriver(a->r,b);
a->r = _aux_merge;
_aux_merge = a;
NodeUpdateSize(a);
}
else {
MergeDriver(a,b->l);
b->l = _aux_merge;
_aux_merge = b;
NodeUpdateSize(b);
}
}
Node* Merge(Node* a, Node* b) {
MergeDriver(a,b);
return _aux_merge;
}
Node* Insert(Node*& root, int pos, int val) {
auto trees = Split(root, pos);
return root = Merge(Merge(trees.first, new Node(val)), trees.second);
}
Node* Remove(Node*& root, int pos) {
auto trees = Split(root,pos);
auto trees_right = Split(trees.second,1);
delete trees_right.first;
return root = Merge(trees.first,trees_right.second);
}
int GetVal(Node* root, int pos, int skipped = 0) {
auto trees = Treap::Split(root,pos);
auto trees_right = Treap::Split(trees.second,1);
int ret = trees_right.first->val;
trees.second = Treap::Merge(trees_right.first,trees_right.second);
root = Treap::Merge(trees.first,trees.second);
return ret;
}
int LowerBound(Node* node, int val, int skipped = 0, int base_size = 0) {
if (!node) return base_size;
int node_key = NodeGetSize(node->l) + skipped;
int new_base_size = ((base_size) ? base_size : NodeGetSize(node));
if (node->val>=val) {
return std::min(node_key, LowerBound(node->l,val,skipped,new_base_size));
}
else {
return LowerBound(node->r,val,node_key+1,new_base_size);
}
}
int UpperBound(Node* node, int val, int skipped = 0, int base_size = 0) {
if (!node) return base_size;
int node_key = NodeGetSize(node->l) + skipped;
int new_base_size = ((base_size) ? base_size : NodeGetSize(node));
if (node->val>val) {
return std::min(node_key, UpperBound(node->l,val,skipped,new_base_size));
}
else {
return UpperBound(node->r,val,node_key+1,new_base_size);
}
}
void Inorder(Node* node, int depth = 0) {
if (!node) {
return;
}
Inorder(node->l,depth+1);
std::cout << node->val << " ";
Inorder(node->r,depth+1);
if (!depth) {
std::cout << "\n";
}
}
}; // namespace Treap
class SetBootleg {
private:
Treap::Node* root = nullptr;
void Print(Treap::Node* node, int depth = 0) {
if (!node) {
return;
}
Print(node->l,depth+1);
std::cout << node->val << " ";
Print(node->r,depth+1);
if (!depth) {
std::cout << "\n";
}
}
public:
void Insert(int val) {
if (!root) {
root = new Treap::Node(val);
return;
}
int pos = Treap::LowerBound(root,val);
Treap::Insert(root,pos,val);
}
void Remove(int val) {
if (!root) {
return;
}
int pos = Treap::LowerBound(root,val);
if (Treap::GetVal(root,pos)!=val) {
return;
}
Treap::Remove(root,pos);
}
int LowerBound(int val) {
return Treap::LowerBound(root,val);
}
int UpperBound(int val) {
return Treap::UpperBound(root,val);
}
int Size() {
return Treap::NodeGetSize(root);
}
void Print() {
Print(root);
}
}; // class SetBootleg
struct SegTreeNode {
SetBootleg set;
SegTreeNode* l = nullptr;
SegTreeNode* r = nullptr;
};
int q, t;
FenwickTree<int> fnwk(200005,1);
SegTreeNode* mst1 = new SegTreeNode; // keeps length of segment in l, so if arr[l] = val, the segment is [l, l+val-1]
SegTreeNode* mst2 = new SegTreeNode; // keeps right side of segment in l
std::pair<int,int> seg[200005];
std::map<std::pair<int,int>,int> map;
void insert(SegTreeNode* node, uint32_t l, uint32_t r, uint32_t pos, int val) {
node->set.Insert(val);
if (l==r) {
return;
}
auto m = (l+r)/2;
if (pos<=m) {
if (!node->l) node->l = new SegTreeNode;
insert(node->l,l,m,pos,val);
}
else {
if (!node->r) node->r = new SegTreeNode;
insert(node->r,m+1,r,pos,val);
}
}
void remove(SegTreeNode* node, uint32_t l, uint32_t r, uint32_t pos, int val) {
if (!node) {
return;
}
node->set.Remove(val);
if (l==r) {
return;
}
auto m = (l+r)/2;
if (pos<=m) {
remove(node->l,l,m,pos,val);
}
else {
remove(node->r,m+1,r,pos,val);
}
}
int query_gteq(SegTreeNode* node, uint32_t l, uint32_t r, uint32_t st, uint32_t fi, int val) {
if (!node) {
return 0;
}
if (l>fi||r<st) {
return 0;
}
if (st<=l&&r<=fi) {
return node->set.Size() - node->set.LowerBound(val);
}
auto m = (l+r)/2;
return query_gteq(node->l,l,m,st,fi,val) + query_gteq(node->r,m+1,r,st,fi,val);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> q >> t;
int last_ans = 0;
int cnt = 0;
while (q--) {
int op;
std::cin >> op;
if (op==1) {
int a, b;
std::cin >> a >> b;
int l = a^(t*last_ans);
int r = b^(t*last_ans);
if (l>r) std::swap(l,r);
++cnt;
seg[cnt] = std::pair<int,int>(l,r);
insert(mst1,0,2000000000,l,r-l+1);
insert(mst2,0,2000000000,l,r);
}
else if (op==2) {
int idx;
std::cin >> idx;
auto [l, r] = seg[idx];
remove(mst1,0,2000000000,l,r-l+1);
remove(mst2,0,2000000000,l,r);
}
else {
int a, b, k;
std::cin >> a >> b >> k;
int l = a^(t*last_ans);
int r = b^(t*last_ans);
if (l>r) std::swap(l,r);
int ret = query_gteq(mst1,0,2000000000,l,r-k+1,k);
if (l>0) {
ret += query_gteq(mst2,0,2000000000,0,l-1,l+k-1);
}
last_ans = ret;
std::cout << ret << "\n";
}
}
}
