Watchmen

Interview

Time limit2sMemory limit1024 MB

Summary

Count pairs of points whose Manhattan distance equals their Euclidean distance, given n points with integer coordinates.

Level: Easy3 of 10
Topics: Hash map, Math
Solved: No attempts yet

Statement

Watchmen are in danger, so Doctor Manhattan and his friend Daniel Dreiberg must warn them as soon as possible. There are $n$ watchmen on a plane, and the $i$ -th watchman is located at point $(x_i, y_i)$ .

Doctor Manhattan measures the distance between watchmen $i$ and $j$ as $|x_i - x_j| + |y_i - y_j|$ . Daniel, an ordinary person, calculates the distance as $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ .

The success of the operation depends on the number of pairs $(i, j)$ ( $1 \leq i < j \leq n$ ) for which the distance computed by Doctor Manhattan equals the distance computed by Daniel. Count these pairs.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 200\,000$ ), the number of watchmen.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ( $|x_i|, |y_i| \leq 10^9$ ).

Output

Print the number of pairs of watchmen whose Manhattan distance equals their Euclidean distance.

Hint

In the first sample, the distance between watchmen 1 and 2 is $|1 - 7| + |1 - 5| = 10$ for Doctor Manhattan and $\sqrt{(1 - 7)^2 + (1 - 5)^2} = 2 \cdot \sqrt{13}$ for Daniel. For the pairs $(1, 1)$ , $(1, 5)$ , $(7, 5)$ , and $(1, 5)$ , Doctor Manhattan and Daniel calculate the same distance.

Examples2

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