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} $$$$$$
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.
Print a single line containing a single integer, denoting the value of $$$ans$$$.
31 2 22 3 13 1 3
75
51 1 45 1 42 3 31 4 12 5 2
1935
