L. Legendary Gyrating Mill
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem shares a setup with Windmill from the $$$2011$$$ IMO, popularized in $$$2019$$$ by 3b1b on YouTube.

You are given $$$n$$$ distinct points $$$P_1, P_2, \ldots, P_n$$$ on the $$$2$$$-d plane. No three points are collinear.

Consider the following process. First you choose a valid starting position, described by a pair $$$(P_i, \ell)$$$, where $$$P_i$$$ is a point and $$$\ell$$$ is an infinite line that intersects $$$P_i$$$, and does not intersect any points other than $$$P_i$$$.

For example, the leftmost and rightmost pictures below are valid starting positions, but the middle one is not ($$$\ell$$$ passes through two points).

$$$\ell$$$ will then rotate clockwise using $$$P_i$$$ as a pivot until it meets another point. The new point, denoted $$$P_j$$$, will then become the new pivot. This process continues indefinitely.

An example of a pivot switch.

Now, consider an undirected graph $$$G$$$ on $$$n$$$ vertices. Initially $$$G$$$ has no edges. Whenever the pivot switches (say, from point $$$P_i$$$ to $$$P_j$$$), then we will add an edge in $$$G$$$ between vertices $$$(i,j)$$$, as long as doing so would not create a cycle. This means that $$$G$$$ will end up as a spanning forest. We denote the spanning forest generated by a starting position $$$(P_i, \ell)$$$ as $$$S(P_i, \ell)$$$.

Of course, you are a programmer, so just calculating $$$S(P_i, \ell)$$$ for a fixed valid starting position would be too easy. So you need to calculate $$$S(P_i, \ell)$$$ across all possible valid starting positions.

There may be infinitely many starting positions, so we will say that two valid starting positions $$$(P_i, \ell)$$$ and $$$(P_i', \ell')$$$ are different if at least one of the following holds:

  • $$$P_i \neq P_i'$$$.
  • Let $$$P_k$$$ be the first new pivot we encounter from the starting position $$$(P_i, \ell)$$$, and define $$$P_k'$$$ similarly. Then, $$$P_k \neq P_k'$$$.

Still, there might be many starting positions, and outputting edges for each of them might be too slow. So, let the edges in some spanning forest $$$S(P_i, \ell)$$$ be $$$(a_1, b_1), (a_2, b_2), \ldots, (a_{\gamma},b_{\gamma})$$$. Then the hash of $$$S(P_i, \ell)$$$ will be the following:

$$$$$$(a_1\cdot b_1) \oplus (a_2 \cdot b_2) \oplus \ldots \oplus (a_{\gamma} \cdot b_{\gamma})$$$$$$

Here $$$\oplus$$$ denotes the bitwise XOR operation.

You need to output the sum of the hashes of all $$$S(P_i, \ell)$$$.

Input

The first line contains an integer $$$n$$$ ($$$3 \le n \le 2\,000$$$).

The following $$$n$$$ lines contain two integers $$$x_i, y_i$$$ each ($$$1 \le x_i, y_i \le 10^9$$$). It is guaranteed that no three points are collinear, and that all points are distinct.

Output

Output the answer, in the format described above.

Examples
Input
3
1 1
3 1
2 2
Output
20
Input
6
2 1
1 2
2 2
3 3
3 4
4 3
Output
492
Note

The first test is a triangle, with $$$6$$$ distinct starting positions. Note that there are $$$3$$$ possible spanning trees on a $$$3$$$-vertex graph.

  • The graph with edges $$$(1,2)$$$ and $$$(2,3)$$$ has a hash of $$$(1 \cdot 2) \oplus (2 \cdot 3) = 4$$$.
  • The graph with edges $$$(1,3)$$$ and $$$(2,3)$$$ has a hash of $$$(1 \cdot 3) \oplus (2 \cdot 3) = 5$$$.
  • The graph with edges $$$(1,2)$$$ and $$$(1,3)$$$ has a hash of $$$(1 \cdot 2) \oplus (1 \cdot 3) = 1$$$.

In fact, we can show that in this test, all of the possible spanning trees are each produced by exactly $$$2$$$ starting positions. So taking the sum, we get $$$4+5+1+4+5+1=20$$$.

In the second test, note that the spanning forest is not necessarily a spanning tree. For example, if we choose the starting position with $$$P_2$$$ and $$$\ell$$$ being a vertical line, the generated spanning forest $$$S(P_2, \ell)$$$ will only have edges $$$(1,2)$$$, $$$(2,5)$$$, and $$$(5,6)$$$.