Toy Animals

Sanggeun and Seonyoung are playing with toy animals. First they pick one of the three game boards below. Each board is made up of many cells; board $1$ is one-dimensional (a line), board $2$ is two-dimensional (a grid), and board $3$ is three-dimensional (a solid grid).

Each cell is identified by integer coordinates, and adjacent cells are joined by a line segment.

• Board $1$: a cell is written as $x$, and cell $x$ is adjacent to cells $x-1$ and $x+1$.
• Board $2$: a cell is written as $(x, y)$, and cell $(x, y)$ is adjacent to $(x\pm1,\ y)$ and $(x,\ y\pm1)$.
• Board $3$: a cell is written as $(x, y, z)$, and cell $(x, y, z)$ is adjacent to $(x\pm1,\ y,\ z)$, $(x,\ y\pm1,\ z)$, and $(x,\ y,\ z\pm1)$.

Sanggeun places $N$ toy animals on the cells. Several animals may share the same cell.

The distance between two cells is the least number of moves needed to travel from one to the other. Because each move goes to an adjacent cell, the distance equals the sum of the absolute differences of the coordinates.

• Board $1$: $|x_1 - x_2|$
• Board $2$: $|x_1 - x_2| + |y_1 - y_2|$
• Board $3$: $|x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|$

Two toy animals can hear each other when the distance between their cells is at most $D$. Given the board type, the position of every toy animal, and $D$, write a program that counts the number of pairs of toy animals that can hear each other.

The first line contains four integers $B$, $N$, $D$, and $M$ separated by spaces.

• $B$ is the board type. ($1 \le B \le 3$)
• $N$ is the number of toy animals. ($1 \le N \le 100,000$)
• $D$ is the greatest distance at which two toy animals can hear each other. ($1 \le D \le 100,000,000$)
• $M$ is the largest value a coordinate can take. If $B = 1$ then $M \le 75,000,000$; if $B = 2$ then $M \le 75,000$; if $B = 3$ then $M \le 75$.

Each of the next $N$ lines gives the coordinates of one toy animal. On board $B$ a line contains $B$ integers separated by spaces: $x$ when $B = 1$, $x\ y$ when $B = 2$, and $x\ y\ z$ when $B = 3$. Every coordinate is a natural number between $1$ and $M$ inclusive. Several animals may occupy the same cell.

Print on the first line the number of pairs of toy animals that can hear each other.