please try to solve the problem

Craziest Prisons and Jails

Some prisons are known for being violent and treating prisoners like animals, leading to inhumane and unethical tactics for keeping the peace. There is a prison located in Norway, Halden is often described as peaceful and relaxing. The prisoners are treated to good food, hot coffee, and cells that boast televisions, mini-fridges, private bathrooms, and scenic views of the surrounding forest.

Norway government build 3 new prisons each one is having its own unique design different from each other. Each prison consists of cells arranged into a one, two or three dimensional grid. Jailer can fill N prisoners into the cells.

The Distance between two cells is the smallest number of moves that a prisoner would need in order to reach one cell from the other. In one move, the prisoner may step into one of the adjacent cells.

Two prisoners can hear each other if the distance between their cells is at most D. Your task is to calculate how many pairs of prisoners there are such that one prisoner can hear the other prisoner.

Example:

Suppose the prison will of 3-dimensional type then it will look like below:

| | | |

| | | |

| | | |

## | | | |

Input Format

Input 1: It will be the integer which tells the type of prison P

Input 2: It will be the integer which tells the number of prisoners N

Input 3: It will be the integer which tells the largest distance D at which two prisoners can hear each other

Input 4: It will be the integer which tells the size of the prison S; (the largest coordinate allowed to appear in the

input):

When P=1, S will be at most 75000000.

When P=2, S will be at most 75000.

When P=3, S will be at most 75.

Input 5: It will be string array which tells the coordinates of each prisoner. Array format will be like:

First line will tell the total number of rows i.e. total number of prisoners N

Each of the following N lines contains P integers separated by single commas - the coordinates of one prisoner.

Each coordinate will be between 1 and S (inclusive). More than one prisoner may occupy the same cell. If the P is

one, then there will be no comma - only single value will be there in each line.

Constraints

1 ≤ P ≤ 3

1 ≤ N ≤ 100000

1 ≤ D ≤ 100000000

Output Format

It will be the single integer, the number of pairs of prisoners that can hear each other.

Sample TestCase 1

Input

38

10

20

8

10,10,10

10,10,20

10,20,10

10,20,20

20,10,10

20,10,20

20,20,10

20,20,20

Output

12

## Top comments (0)