Problem Description

Mirko and Slavko are playing a game with animal toys. First, they choose one of the three toy templates shown in the figure below. The three templates are made of 1D, 2D, and 3D grid points (shown as circles in the figure).

Next, Mirko places $N$ small animal toys onto the grid points of the chosen template.

An animal toy can move one step to a grid point adjacent to it (in the figure, adjacent points are connected by a short line). The distance between two grid points is defined as the minimum number of steps needed to move from one grid point to the other.

If the distance between two animals is less than or equal to $D$, then they can hear each other. Slavko’s task is to count how many pairs of animals on the template can hear each other.

Given the template type, the positions of all animals, and the number $D$, write a program to compute how many pairs of animal toys can hear each other.

Input Format

The first line of input contains four integers in order:

• Template type $B (1 \leq B \leq 3)$;
• Number of animal toys $N (1 \leq N \leq 100 000)$;
• Maximum distance at which two animals can hear each other $D (1 \leq D \leq 100 000 000)$;
• Template size $M$ (i.e., the maximum coordinate value allowed in the input): when $B=1$, the maximum $M$ is $75 000 000$; when $B=2$, the maximum $M$ is $75 000$; when $B=3$, the maximum $M$ is $75$.

The next $N$ lines each contain $B$ integers separated by spaces, representing the coordinates of an animal toy. Each coordinate ranges from $1$ to $M$ (including $M$).

Each grid point may contain multiple animal toys at the same time.

Output Format

Output one integer, the number of pairs of animal toys that can hear each other.

Note: use a 64-bit integer type to compute and output the result (use long long in C/C++, and int64 in Pascal).

1 6 5 100 
25 
50 
50 
10 
20 
23 

4

2 5 4 10 
5 2 
7 2 
8 4 
6 5 
4 4 

8

3 8 10 20 
10 10 10 
10 10 20 
10 20 10 
10 20 20 
20 10 10 
20 10 20 
20 20 10 
20 20 20 

12

Hint

In the testdata worth 30 points, the number of animals $N$ is at most $1 000$.

If you pass all testdata for any one template type (1D, 2D, or 3D), you will get at least 30 points.

Explanation for input 1: Suppose the animals are numbered from $1$ to $6$ in the given order. The $4$ pairs of animals that can hear each other are:

• 1-5 (distance is 5)
• 1-6 (distance is 2)
• 2-3 (distance is 0)
• 5-6 (distance is 3)

Explanation for input 2: The $8$ pairs of animals are:

• 1-2 (distance is 2)
• 1-4 (distance is 4)
• 1-5 (distance is 3)
• 2-3 (distance is 3)
• 2-4 (distance is 4)
• 3-4 (distance is 3)
• 3-5 (distance is 4)
• 4-5 (distance is 3)

Translated by ChatGPT 5