#include <iostream>
#include <algorithm>
#include <vector>
struct Event
{
Event(int p, int t, int l, int r, int s) : pos(p), type(t), left(l), right(r), squ(s) {}
int pos, type, left, right, squ;
bool operator <(const Event &other) const
{
if (pos != other.pos)
return (pos < other.pos);
return (type < other.type);
}
};
const int MAXN = 1e5;
const int TSIZE = 5e5;
//Subtask 1
int animals[MAXN];
//Subtask 2
int tree[TSIZE];
std::vector<Event> squares;
long long first[MAXN], count[MAXN];
//Subtask 3
std::vector<Event> decomp[76];
long long cnt[MAXN];
void oned(int toys, int maxDist)
{
for (int iToy = 0; iToy < toys; iToy++)
std::cin >> animals[iToy];
std::sort(animals, animals + toys);
long long ans = 0, last = 0;
for (long long iToy = 0; iToy < toys; iToy++)
{
while (animals[iToy] - animals[last] > maxDist)
last++;
ans += iToy - last;
}
std::cout << ans << '\n';
}
void add(int u)
{
while (u < TSIZE)
{
tree[u]++;
u += u & (-u);
}
}
int sum(int u)
{
int r = 0;
while (u > 0)
{
r += tree[u];
u -= u & (-u);
}
return r;
}
void countinsqr()
{
std::fill_n(tree, TSIZE, 0);
std::sort(squares.begin(), squares.end());
for (Event &ev : squares)
{
if (ev.type == -1)
first[ev.squ] = sum(ev.right) - sum(ev.left);
else if (ev.type == 1)
count[ev.squ] = sum(ev.right) - sum(ev.left) - first[ev.squ];
else
add(ev.left);
}
}
void twod(int toys, int maxDist)
{
for (int iToy = 0; iToy < toys; iToy++)
{
int a, b;
std::cin >> a >> b;
int x = b - a, y = b + a;
squares.emplace_back(x - maxDist, -1, y, y + 2 * maxDist + 1, iToy);
squares.emplace_back(x + maxDist, 1, y, y + 2 * maxDist + 1, iToy);
squares.emplace_back(x, 0, y + maxDist + 1, -1, -1);
}
countinsqr();
long long ans = 0;
for (int iToy = 0; iToy < toys; iToy++)
ans += count[iToy] - 1LL;
std::cout << ans / 2LL << '\n';
}
void threed(int toys, int maxDist)
{
for (int iToy = 0; iToy < toys; iToy++)
{
int a, b, c;
std::cin >> a >> b >> c;
int x = b - a, y = b + a;
decomp[c].emplace_back(x, 0, y + maxDist + 1, -1, -1);
for (int iDelt = 0; iDelt <= maxDist && c > iDelt; iDelt++)
{
int d = maxDist - iDelt;
decomp[c - iDelt].emplace_back(x - d, -1, y + iDelt, y + maxDist + d + 1, iToy);
decomp[c - iDelt].emplace_back(x + d, 1, y + iDelt, y + maxDist + d + 1, iToy);
}
for (int iDelt = 1; iDelt <= maxDist && c + iDelt < 76; iDelt++)
{
int d = maxDist - iDelt;
decomp[c + iDelt].emplace_back(x - d, -1, y + iDelt, y + maxDist + d + 1, iToy);
decomp[c + iDelt].emplace_back(x + d, 1, y + iDelt, y + maxDist + d + 1, iToy);
}
}
for (int iDepth = 1; iDepth < 76; iDepth++)
{
std::fill_n(count, toys, 0);
squares = decomp[iDepth];
countinsqr();
for (int iToy = 0; iToy < toys; iToy++)
cnt[iToy] += count[iToy];
}
long long ans = 0;
for (int iToy = 0; iToy < toys; iToy++)
ans += cnt[iToy] - 1LL;
std::cout << ans / 2LL << '\n';
}
int main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
int boardType, toys, maxDist, boardSize;
std::cin >> boardType >> toys >> maxDist >> boardSize;
if (boardType == 1)
oned(toys, std::min(maxDist, boardSize - 1));
else if (boardType == 2)
twod(toys, std::min(maxDist, (boardSize - 1) * 2));
else
threed(toys, std::min(maxDist, (boardSize - 1) * 3));
return 0;
}
