// first time implementing batching btw
// because nsqrtlog is apparently better nlog^2
// because it uses less memory, gg nice logic
// WTF?? BRUTE FORCE GETS 75 BUT NLOG^2 WITH
// MERGE SORT TREAP GETS 7 BECAUSE MEMORY LOL
// oh ffs here we go again using a merge sort fking tree
// instead of sqrt decomp even though its the same overall complexity
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#endif
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <random>
const int BLK_SIZE = 450;
int q, t;
std::pair<int,int> seg[200005];
std::vector<int> arr_l;
std::vector<int> arr_r;
std::vector<int> arr_len;
std::vector<int> mst_r[400005];
std::vector<int> mst_len[400005];
bool in_ds[200005];
bool active[200005];
bool to_remove[200005];
std::vector<int> brute1;
std::vector<int> brute2;
int intersection_size(int l1, int r1, int l2, int r2) {
return std::min(r1,r2) - std::max(l1,l2) + 1;
}
void build_tree(std::vector<int>* mst, const std::vector<int>& arr, int node, int l, int r) {
mst[node].clear();
if (l==r) {
mst[node].emplace_back(arr[l]);
return;
}
int m = (l+r)>>1;
build_tree(mst,arr,node<<1,l,m);
build_tree(mst,arr,node<<1|1,m+1,r);
std::merge(mst[node<<1].begin(),mst[node<<1].end(),
mst[node<<1|1].begin(),mst[node<<1|1].end(),
std::back_inserter(mst[node]));
}
int query_gteq(std::vector<int>* mst, int node, int l, int r, int st, int fi, int val) {
if (l>fi||r<st) {
return 0;
}
if (st<=l&&r<=fi) {
return mst[node].size() - (std::lower_bound(mst[node].begin(),mst[node].end(),val)-mst[node].begin());
}
int m = (l+r)>>1;
return query_gteq(mst,node<<1,l,m,st,fi,val) + query_gteq(mst,node<<1|1,m+1,r,st,fi,val);
}
void recalculate() {
std::vector<int> tmp;
for (int i = 1; i <= q; i++) {
if (active[i]&&!to_remove[i]) {
tmp.emplace_back(i);
//arr_l.emplace_back(seg[i].l);
//arr_r.emplace_back(seg[i].r);
}
}
std::sort(tmp.begin(),tmp.end(),[&](int a, int b) {
if (seg[a].first!=seg[b].first) return seg[a].first < seg[b].first;
return seg[a].second < seg[b].second;
});
// cleanup
brute1.clear();
brute2.clear();
arr_l.clear();
arr_r.clear();
arr_len.clear();
for (int i = 1; i <= q; i++) {
in_ds[i] = 0;
to_remove[i] = 0;
}
for (const auto& i : tmp) {
in_ds[i] = 1;
arr_l.emplace_back(seg[i].first);
arr_r.emplace_back(seg[i].second);
arr_len.emplace_back(seg[i].second-seg[i].first+1);
}
build_tree(mst_r,arr_r,1,0,arr_l.size()-1);
build_tree(mst_len,arr_len,1,0,arr_l.size()-1);
}
int brute_answer(int l, int r, int k) {
int ret = 0;
for (const auto& i : brute1) {
ret += (intersection_size(l,r,seg[i].first,seg[i].second)>=k);
}
return ret;
}
int brute_answer2(int l, int r, int k) {
int ret = 0;
for (const auto& i : brute2) {
ret += (intersection_size(l,r,seg[i].first,seg[i].second)>=k);
}
return ret;
}
int ds_answer(int l, int r, int k) {
if (!arr_l.size()) {
return 0;
}
const auto bs1 = [&]() {
int ret = arr_r.size();
int ll = 0, rr = arr_r.size()-1;
while (ll<=rr) {
int m = (ll+rr)>>1;
if (arr_l[m]>=l) {
ret = m;
rr = m-1;
}
else {
ll = m+1;
}
}
return ret;
};
const auto bs2 = [&]() {
int ret = -1;
int ll = 0, rr = arr_r.size()-1;
while (ll<=rr) {
int m = (ll+rr)>>1;
if (arr_l[m]<=r-k+1) {
ret = m;
ll = m+1;
}
else {
rr = m-1;
}
}
return ret;
};
const auto bs3 = [&]() {
int ret = -1;
int ll = 0, rr = arr_r.size()-1;
while (ll<=rr) {
int m = (ll+rr)>>1;
if (arr_l[m]<l) {
ret = m;
ll = m+1;
}
else {
rr = m-1;
}
}
return ret;
};
// left segment inside [l, r]
int ret = 0;
int le = bs1();
int ri = bs2();
if (le<=ri) {
ret += query_gteq(mst_len,1,0,arr_l.size()-1,le,ri,k);
}
// left segment outside [l, r]
le = 0;
ri = bs3();
if (le<=ri) {
ret += query_gteq(mst_r,1,0,arr_l.size()-1,le,ri,l+k-1);
}
return ret;
}
void print(const std::vector<int>& arr, const char* const msg) {
std::cout << msg << ": ";
for (const auto& i : arr) {
std::cout << i << " ";
}
std::cout << "\n";
}
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;
for (int i = 0; i < q; i++) {
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);
brute1.emplace_back(cnt);
active[cnt] = 1;
}
else if (op==2) {
int idx;
std::cin >> idx;
auto [l, r] = seg[idx];
if (in_ds[idx]) {
to_remove[idx] = 1;
brute2.emplace_back(idx);
}
else {
auto it = std::find(brute1.begin(),brute1.end(),idx);
if (it!=brute1.end()) {
brute1.erase(it);
}
}
active[idx] = 0;
}
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 = ds_answer(l,r,k) + brute_answer(l,r,k) - brute_answer2(l,r,k);
std::cout << (last_ans = ret) << "\n";
}
#ifdef DBG
print(arr_l,"arr_l");
print(arr_r,"arr_r");
print(arr_len,"arr_len");
print(brute1,"brute1");
print(brute2,"brute2");
std::cout << "\n";
#endif
if ((i+1)%BLK_SIZE==0) {
recalculate();
}
}
#ifdef DBG
print(arr_l,"arr_l");
print(arr_r,"arr_r");
print(arr_len,"arr_len");
print(brute1,"brute1");
print(brute2,"brute2");
std::cout << "\n";
#endif
}
