#pragma GCC optimize("O5,unroll-loops,inline,fast-math") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include<bits/stdc++.h> #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) #define int long long using namespace std; int b,n,d,m,ans,p,q,r,f[150005],fw[305][305][305]; struct pt { int c[4]; bool operator<(const pt &other) const { for (int i = 0; i < 4; i++) if (c[i]^other.c[i]) return c[i] < other.c[i]; return 0; } } pt[100005]; void u(int pos, int x) {for (int i = pos; i < 150005; i += i&-i) f[i] += x;} int qu(int pos) { int sum=0; for (int i = pos; i > 0; i -= i&-i) sum += f[i]; return sum; } int rq(int l, int r) {l=max(1LL,l);r=min(150004LL,r);return l>r?0:qu(r)-qu(l-1);} void up(int x, int y, int z, int del) {for (int i = x; i < 305; i+=i&-i) for (int j = y; j < 305; j+=j&-j) for (int k = z; k < 305; k+=k&-k) fw[i][j][k] += del;} int qe(int x, int y, int z) { int sum = 0; for (int i = x; i > 0; i-=i&-i) for (int j = y; j > 0; j-=j&-j) for (int k = z; k > 0; k-=k&-k) sum += fw[i][j][k]; return sum; } int r3(int x1, int y1, int z1, int x2, int y2, int z2) {x1=max(1LL,x1);x2=min(304LL,x2);y1=max(1LL,y1);y2=min(304LL,y2);z1=max(1LL,z1);z2=min(304LL,z2);if(x1>x2||y1>y2||z1>z2)return 0;x1--;y1--;z1--;return qe(x2,y2,z2)-qe(x1,y2,z2)-qe(x2,y1,z2)-qe(x2,y2,z1)+qe(x1,y1,z2)+qe(x1,y2,z1)+qe(x2,y1,z1)-qe(x1,y1,z1);} signed main(void) { exoworldgd; int l,r; cin >> b >> n>> d >> m; if(b==1){ for (int i =0; i< n; i++) cin >> pt[i].c[0]; sort(pt,pt+n),l=0; for (r =0; r <n; r++) { while (pt[r].c[0]-pt[l].c[0] > d) l++; ans += r-l; } }else if(b==2){ for (int i = 0; i <n; i++) cin >>p >> q, pt[i].c[0]=p-q,pt[i].c[1]=p+q; sort(pt,pt+n),l=0; for (r=0; r <n ; r++) { while (pt[r].c[0]-pt[l].c[0] > d) u(pt[l].c[1],-1), l++; ans += rq(pt[r].c[1]-d,pt[r].c[1]+d),u(pt[r].c[1],1); } }else{ for (int i = 0; i <n; i++) cin >> p >> q >> r, pt[i].c[0]=p+q+r+150, pt[i].c[1]=p+q-r+150, pt[i].c[2]=p-q+r+150, pt[i].c[3]=p-q-r+150; sort(pt,pt+n),l=0; for (r=0; r <n; r++) { while (pt[r].c[0]-pt[l].c[0] > d) up(pt[l].c[1],pt[l].c[2],pt[l].c[3],-1), l++; ans += r3(pt[r].c[1]-d,pt[r].c[2]-d,pt[r].c[3]-d,pt[r].c[1]+d,pt[r].c[2]+d,pt[r].c[3]+d),up(pt[r].c[1],pt[r].c[2],pt[r].c[3],1); } } cout << ans; }