Good Triangle

Time limit2sMemory limit1024 MB

Summary

Count the triples of distinct points for which some point T is equidistant from all three under Manhattan distance, with up to 500000 points.

Level: Medium7 of 10
Topics: Geometry, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

You are given $n$ distinct points on the two dimensional plane.

The distance between two points $P=(x_1, y_1)$ and $Q=(x_2, y_2)$ is $d(P, Q)=|x_1-x_2|+|y_1-y_2|$ .

Three distinct points $U, V, W$ form a good triangle if there exists a point $T$ such that $d(U, T)=d(V, T)=d(W, T)$ . $T$ does not have to be a lattice point.

Find the number of good triangles that can be formed from the given points.

Input

The first line contains $N$ . Each of the next $N$ lines contains two space-separated integers $x_i, y_i$ , the coordinates of the $i$ -th point.

Output

Print one integer, the number of good triangles.

Constraints

$3 \leq N \leq 500\,000$
$-10^9 \leq x_i, y_i \leq 10^9$ ( $1 \leq i \leq N$ )
$(x_i, y_i) \neq (x_j, y_j)$ if $i \neq j$ ( $1 \leq i, j \leq N$ )
All values in the input are integers.

Examples2

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

Example 2

Input

Expected output