Toy Animals

Time limit2sMemory limit128 MB

Summary

Count pairs of points on a 1D, 2D, or 3D integer grid whose Manhattan distance is at most D.

Level: Hard8 of 10
Topics: Divide and conquer, Sorting, Geometry, Bit manipulation
Solved: No attempts yet

Problem

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).

game boards

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.

Input

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.

Output

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

Examples7

Example 1
Input
```
2 5 4 10
5 2
7 2
8 4
6 5
4 4
```
Expected output
```
8
```
Example 2
Input
```
1 4 3 100
1
2
5
9
```
Expected output
```
2
```
Example 3
Input
```
1 5 1 10
3
3
3
3
3
```
Expected output
```
10
```

Example 4

Input

1 6 100000000 75000000
1
100
50000000
2
75000000
999

Expected output

Example 5
Input
```
2 4 1 10
1 1
1 2
2 1
2 2
```
Expected output
```
4
```

Example 6

Input

2 5 100000000 75000
1 1
75000 75000
1 75000
40000 40000
2 3

Expected output

Example 7
Input
```
3 4 2 5
1 1 1
2 1 1
1 2 2
3 3 3
```
Expected output
```
2
```