H. Points Selection
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ points $$$p_1,p_2,\dots,p_n$$$ on the 2D plane. The $$$i$$$-th point $$$p_i$$$ is located at $$$(x_i,y_i)$$$ with weight $$$w_i$$$.

Consider a query with parameters $$$(a,b,c)$$$, let $$$S(a,b)=\{p_i|x_i\leq a\land y_i\leq b\}$$$. The query denotes "Is it possible to select a subset $$$T$$$ from $$$S$$$ such that $$$(\sum_{p_i\in T}w_i)\bmod n=c$$$?" ($$$T\subseteq S$$$)

Let $$$\text{query}(a,b,c)=\text{True/False}$$$ be the answer to the query with parameters $$$(a,b,c)$$$. You are required to answer all possible queries. Instead of printing $$$O(n^3)$$$ lines, you only need to compute the following value:

$$$$$$ ans=(\sum_{a=1}^n\sum_{b=1}^n\sum_{c=1}^{n-1} a\cdot b\cdot c\cdot[\text{query}(a,b,c)=\text{True}])\bmod 2^{64} $$$$$$

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 5\times 10^5$$$), denoting the number of points.

In the next $$$n$$$ lines, the $$$i$$$-th line contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1\leq x_i,y_i,w_i\leq n$$$), describing the $$$i$$$-th point. Note that two points may share the same location.

It is guaranteed that all the values of $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ are chosen uniformly at random from integers in their corresponding ranges. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.

Output

Print a single line containing a single integer, denoting the value of $$$ans$$$.

Examples
Input
3
1 2 2
2 3 1
3 1 3
Output
75
Input
5
1 1 4
5 1 4
2 3 3
1 4 1
2 5 2
Output
1935