// Chat gpt's code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
array<int, 2> id[N];
struct Interval {
int l, r, len, id;
};
struct Block {
vector<Interval> a; // sorted by (l, id)
vector<int> ends; // sorted
vector<int> lens; // sorted
int minL = 0, maxL = 0;
void rebuild() {
if (a.empty()) {
ends.clear();
lens.clear();
minL = maxL = 0;
return;
}
minL = a.front().l;
maxL = a.back().l;
ends.clear();
lens.clear();
ends.reserve(a.size());
lens.reserve(a.size());
for (auto &x : a) {
ends.push_back(x.r);
lens.push_back(x.len);
}
sort(ends.begin(), ends.end());
sort(lens.begin(), lens.end());
}
};
static const int B = 700;
vector<Block> blocks;
int ID = 1;
int last = 0;
bool cmpInterval(const Interval &x, const Interval &y) {
if (x.l != y.l) return x.l < y.l;
return x.id < y.id;
}
int find_pos(int l) {
int lo = 0, hi = (int)blocks.size();
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (blocks[mid].maxL < l) lo = mid + 1;
else hi = mid;
}
return lo;
}
int find_block_containing(int l) {
int pos = find_pos(l);
if (pos < (int)blocks.size() && blocks[pos].minL <= l && l <= blocks[pos].maxL) return pos;
if (pos > 0 && blocks[pos - 1].minL <= l && l <= blocks[pos - 1].maxL) return pos - 1;
return -1;
}
void split_block(int idx) {
Block &b = blocks[idx];
if ((int)b.a.size() <= 2 * B) return;
int mid = (int)b.a.size() / 2;
int splitL = b.a[mid].l;
while (mid < (int)b.a.size() && b.a[mid].l == splitL) mid++;
// Avoid splitting equal-l values across blocks.
if (mid == 0 || mid == (int)b.a.size()) return;
Block right;
right.a.assign(b.a.begin() + mid, b.a.end());
b.a.erase(b.a.begin() + mid, b.a.end());
b.rebuild();
right.rebuild();
blocks.insert(blocks.begin() + idx + 1, std::move(right));
}
void maybe_merge(int idx) {
if (blocks.empty()) return;
if (idx >= (int)blocks.size()) idx = (int)blocks.size() - 1;
if ((int)blocks[idx].a.size() >= B / 2) return;
int left = -1, right = -1;
if (idx + 1 < (int)blocks.size() &&
(int)blocks[idx].a.size() + (int)blocks[idx + 1].a.size() <= 2 * B) {
left = idx;
right = idx + 1;
} else if (idx > 0 &&
(int)blocks[idx].a.size() + (int)blocks[idx - 1].a.size() <= 2 * B) {
left = idx - 1;
right = idx;
}
if (right == -1) return;
Block merged;
merged.a.reserve(blocks[left].a.size() + blocks[right].a.size());
merged.a = blocks[left].a;
merged.a.insert(merged.a.end(), blocks[right].a.begin(), blocks[right].a.end());
merged.rebuild();
blocks.erase(blocks.begin() + right);
blocks[left] = std::move(merged);
}
void add(int l, int r) {
Interval iv{l, r, r - l + 1, ID};
id[ID++] = {l, r};
if (blocks.empty()) {
Block b;
b.a.push_back(iv);
b.rebuild();
blocks.push_back(std::move(b));
return;
}
int pos = find_pos(l);
// If l is in a gap, create a new block there.
if (pos == (int)blocks.size() || !(blocks[pos].minL <= l && l <= blocks[pos].maxL)) {
Block b;
b.a.push_back(iv);
b.rebuild();
blocks.insert(blocks.begin() + pos, std::move(b));
return;
}
Block &b = blocks[pos];
auto it = lower_bound(b.a.begin(), b.a.end(), iv, cmpInterval);
b.a.insert(it, iv);
auto itR = lower_bound(b.ends.begin(), b.ends.end(), r);
b.ends.insert(itR, r);
auto itL = lower_bound(b.lens.begin(), b.lens.end(), iv.len);
b.lens.insert(itL, iv.len);
b.minL = b.a.front().l;
b.maxL = b.a.back().l;
if ((int)b.a.size() > 2 * B) split_block(pos);
}
void remove(int rem) {
int l = id[rem][0];
int r = id[rem][1];
int len = r - l + 1;
int pos = find_block_containing(l);
if (pos == -1) return;
Block &b = blocks[pos];
Interval key{l, r, len, rem};
auto it = lower_bound(b.a.begin(), b.a.end(), key, cmpInterval);
if (it != b.a.end() && it->l == l && it->id == rem) {
b.a.erase(it);
}
auto itR = lower_bound(b.ends.begin(), b.ends.end(), r);
if (itR != b.ends.end() && *itR == r) b.ends.erase(itR);
auto itL = lower_bound(b.lens.begin(), b.lens.end(), len);
if (itL != b.lens.end() && *itL == len) b.lens.erase(itL);
if (b.a.empty()) {
blocks.erase(blocks.begin() + pos);
return;
}
b.minL = b.a.front().l;
b.maxL = b.a.back().l;
maybe_merge(pos);
}
int cnt(int l, int r) {
int ans = 0;
for (auto &b : blocks) {
if (b.minL > l) break;
if (b.maxL <= l) {
auto it = lower_bound(b.ends.begin(), b.ends.end(), r);
ans += (int)(b.ends.end() - it);
} else {
for (auto &iv : b.a) {
if (iv.l <= l && iv.r >= r) ans++;
}
}
}
return ans;
}
int cnt_sz(int l, int r, int k) {
if (l > r) return 0;
int ans = 0;
for (auto &b : blocks) {
if (b.maxL < l) continue;
if (b.minL > r) break;
if (b.minL >= l && b.maxL <= r) {
auto it = lower_bound(b.lens.begin(), b.lens.end(), k);
ans += (int)(b.lens.end() - it);
} else {
for (auto &iv : b.a) {
if (iv.l >= l && iv.l <= r && iv.len >= k) ans++;
}
}
}
return ans;
}
void solve() {
int q, t;
cin >> q >> t;
blocks.reserve(1000);
while (q--) {
int tip;
cin >> tip;
if (tip == 1) {
int a, b;
cin >> a >> b;
int l = a ^ (t * last);
int r = b ^ (t * last);
if (l > r) swap(l, r);
add(l, r);
continue;
}
if (tip == 2) {
int rem;
cin >> rem;
remove(rem);
continue;
}
int a, b, k;
cin >> a >> b >> k;
int l = a ^ (t * last);
int r = b ^ (t * last);
if (l > r) swap(l, r);
if (r - l + 1 < k) {
last = 0;
cout << last << '\n';
continue;
}
last = cnt(l - 1, l + k - 1) + cnt_sz(l, r - k + 1, k);
cout << last << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
