#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LLONG_MAX
#define LMIN LLONG_MIN
#define MOD 1000000007
#define SIR 1000000009
struct pt {
int x = 0, y = 0, z = 0;
pt() {};
pt(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {};
void rotate() {
int ox = x, oy = y;
x = ox - oy;
y = ox + oy;
}
};
bool operator<(pt a, pt b) {
auto A = make_tuple(a.x, a.y, a.z);
auto B = make_tuple(b.x, b.y, b.z);
return A < B;
}
struct npt {
int a = 0, b = 0, c = 0, d = 0;
npt() {}
npt(pt p) {
auto [x, y, z] = p;
a = x + y + z;
b = x + y - z + 75;
c = x - y + z + 75;
d = -x + y + z + 75;
}
};
bool operator<(npt a, npt b) {
auto A = make_tuple(a.a, a.b, a.c, a.d);
auto B = make_tuple(b.a, b.b, b.c, b.d);
return A < B;
}
struct Fenwick {
int n;
vi vals;
Fenwick(int _n) : n(_n) {
vals = vi(n, 0);
}
void update(int i, int d) {
while (i < n) {
vals[i] += d;
i |= (i + 1);
}
}
int sum(int i) {
if (i < 0) return 0;
int res = 0;
while (i >= 0) {
res += vals[i];
i = (i & (i + 1)) - 1;
}
return res;
}
int sum(int a, int b) { // sum[a,..b]
if (b >= n) b = n - 1;
if (a > b) return 0;
return sum(b) - sum(a - 1);
}
};
struct Fenwick3d {
int sz;
vector<vector<vi>> vals;
Fenwick3d(int n) : sz(n) {
vals = vector(sz, vector(sz, vi(sz, 0)));
}
void update(int i, int j, int k, int d) {
auto g = [&](int& x) { x |= (x + 1); };
int ai = i;
while (ai < sz) {
int aj = j;
while (aj < sz) {
int ak = k;
while (ak < sz) {
vals[ai][aj][ak] += d;
g(ak);
}
g(aj);
}
g(ai);
}
}
int sum(int i, int j, int k) {
if (i < 0 || j < 0 || k < 0) return 0;
int res = 0;
auto g = [&](int& x) { x = (x & (x + 1)) - 1; };
int ai = i;
while (ai >= 0) {
int aj = j;
while (aj >= 0) {
int ak = k;
while (ak >= 0) {
res += vals[ai][aj][ak];
g(ak);
}
g(aj);
}
g(ai);
}
return res;
}
int sum(int x1, int y1, int z1, int x2, int y2, int z2) {
x2 = min(x2, sz - 1);
y2 = min(y2, sz - 1);
z2 = min(z2, sz - 1);
if (x2 < x1) return 0;
if (y2 < y1) return 0;
if (z2 < z1) return 0;
int res = sum(x2, y2, z2) - sum(x1 - 1, y2, z2) - sum(x2, y1 - 1, z2) - sum(x2, y2, z1 - 1) + sum(x1 - 1, y1 - 1, z2) + sum(x2, y1 - 1, z1 - 1) + sum(x1 - 1, y2, z1 - 1) - sum(x1 - 1, y1 - 1, z1 - 1);
return res;
}
};
int t, n, D, M;
vector<pt> pts;
int dist(pt a, pt b) {
return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z-b.z));
}
void d1() {
ll res = 0;
deque<int> akt;
sort(all(pts));
for (int i = 0; i < n; i++) {
pt& cur = pts[i];
while (!akt.empty() && dist(cur, pts[akt.front()]) > D) {
akt.pop_front();
}
res += akt.size();
akt.pb(i);
}
cout << res << '\n';
}
void d2() {
auto nah = [&](int a, int b) { return (abs(pts[a].x - pts[b].x) <= D); };
for (auto& p : pts) p.rotate();
sort(all(pts));
Fenwick F(150001);
int l = 0, r = 0;
ll res = 0;
while (l < n) {
if (r != n && nah(l, r)) {
res += F.sum(pts[r].y - D, pts[r].y + D);
F.update(pts[r].y, 1);
r++;
} else {
F.update(pts[l].y, -1);
l++;
}
}
cout << res << '\n';
}
void d3() {
int prefs[76][155][155] = {0};
for (auto& p : pts) {
p.rotate();
p.x += 75;
auto [x, y, z] = p;
prefs[z][x][y]++;
}
for (int i = 1; i < 76; i++) {
for (int j = 1; j < 155; j++) {
for (int k = 1; k < 155; k++) {
prefs[i][j][k] += prefs[i][j - 1][k] + prefs[i][j][k - 1] - prefs[i][j - 1][k - 1];
}
}
}
auto zisti = [&](int z, int x1, int y1, int x2, int y2) {
x1 = max(1, x1);
x2 = min(x2, 154);
y1 = max(1, y1);
y2 = min(y2, 154);
if (x1 > x2 || y1 > y2) return 0;
int ans = prefs[z][x1 - 1][y1 - 1] + prefs[z][x2][y2] - prefs[z][x2][y1 - 1] - prefs[z][x1 - 1][y2];
return ans;
};
ll res = 0;
for (auto [x, y, z] : pts) {
for (int i = 0; i < 76; i++) {
int maxd = D - abs(z - i);
res += zisti(i, x - maxd, y - maxd, x + maxd, y + maxd);
}
}
res = (res - n) / 2;
cout << res << '\n';
}
void solve() {
Fenwick3d F(305);
vector<npt> npts(n);
for (int i = 0; i < n; i++) {
npts[i] = npt(pts[i]);
}
auto nah = [&](int a, int b) { return (abs(npts[a].a - npts[b].a) <= D); };
sort(all(npts));
ll res = 0;
int l = 0, r = 0;
while (l < n) {
if (r != n && nah(l, r)) {
auto [a, b, c, d] = npts[r];
res += F.sum(b - D, c - D, d - D, b + D, c + D, d + D);
F.update(b, c, d, 1);
r++;
} else {
auto [a, b, c, d] = npts[l];
F.update(b, c, d, -1);
l++;
}
}
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t >> n >> D >> M;
pts.resize(n);
for (int i = 0; i < n; i++) {
int x = 0, y = 0, z = 0;
if (t == 1) cin >> x;
if (t == 2) cin >> x >> y;
if (t == 3) cin >> x >> y >> z;
pts[i] = pt(x, y, z);
}
if (t == 1)
d1();
else if (t == 2)
d2();
else
solve(); // or d3()
return 0;
}
