Problem Description

Mirko and Slavko are playing with animal toys. First, they need to choose one of the three toy templates provided below. These templates consist of one-dimensional, two-dimensional, and three-dimensional grid points (represented by circles in the diagram).

Next, Mirko places \( N \) small animal toys on the chosen template's grid points.

Animal toys can move one step to an adjacent grid point (adjacent points are connected by a small line in the diagram). The distance between two grid points is defined as the minimum number of steps required to move from one point to the other.

If the distance between two animals is less than or equal to \( D \), they can hear each other. Slavko's task is to calculate how many pairs of animals on the template can hear each other.

Given the type of template, the positions of all animals, and the number \( D \), write a program to calculate how many pairs of animals 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 toy animals \( N (1 \leq N \leq 100,000) \);
- Maximum distance \( D (1 \leq D \leq 100,000,000) \) at which animals can hear each other;
- Size of the template \( M \) (the maximum allowed coordinate value): When \( B=1 \), \( M \) is at most \( 75,000,000 \). When \( B=2 \), \( M \) is at most \( 75,000 \). When \( B=3 \), \( M \) is at most \( 75 \).

The next \( N \) lines each contain \( B \) integers separated by spaces, representing the coordinates of an animal toy. The coordinates range from \( 1 \) to \( M \) (inclusive).

Multiple animal toys can occupy the same grid point.

Output Format

The output should include a single integer, representing the number of pairs of toy animals that can hear each other.

Note: Use 64-bit integer types for calculations and output (use long long in C/C++, and int64 in Pascal).

Sample Input and Output

Sample Input #1

1 6 5 100
25
50
50
10
20
23

Sample Output #1

4

Sample Input #2

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

Sample Output #2

8

Sample Input #3

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

Sample Output #3

12

Notes/Hints

In test cases worth 30 points, the number of animals \( N \) is at most \( 1,000 \).

If you successfully pass all test data for one type of template (one-dimensional, two-dimensional, or three-dimensional), you will receive at least 30 points.

Explanation for Input 1: Assuming the animals are numbered from 1 to 6 in the given order. The 4 pairs 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)

见题面 Input 部分

见题面 Output 部分