Stupendous Bowties

Time limit2sMemory limit512 MB

Summary

Given N distinct integer points, count unordered pairs of axis-aligned right triangles that share only the right-angle vertex.

Level: Medium6 of 10
Topics: Geometry, Combinatorics, Hash map, Math
Solved: No attempts yet

Problem

There are $N$ distinct points on the plane. The $i$ -th point sits at integer coordinates $(x_i, y_i)$ .

A Fantastic Right Triangle uses three of the given points as its vertices, has positive area, and has both of its legs parallel to the axes: one leg is parallel to the $x$ -axis and the other is parallel to the $y$ -axis. The vertex where the two legs meet, the one whose interior angle is right, is called the triangle's Spectacular Vertex.

A Stupendous Bowtie is an unordered pair of Fantastic Right Triangles that share the same Spectacular Vertex and touch only at that point. Treat each triangle as a closed region that includes its boundary and its interior, so the pair forms a bowtie only when the intersection of the two triangles is exactly that shared vertex.

Count the Stupendous Bowties that exist among the given points.

Input

The first line contains the number of points $N$ .

Each of the next $N$ lines contains two integers $x_i$ and $y_i$ separated by a space.

Output

Print, on a single line, the number of Stupendous Bowties that exist among the given points.

Limits

$1 \le N \le 100\,000$
$-100\,000 \le x_i \le 100\,000$
$-100\,000 \le y_i \le 100\,000$
The $N$ given points are pairwise distinct.
The answer can exceed the range of a 32-bit integer.

Examples4

Example 1

Input

12
-3 6
1 6
-1 4
-3 2
1 2
4 2
-4 -3
-3 -3
1 -3
-1 -4
1 -4
-3 -6

Expected output

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