在二维平面上有 $n$ 个点 $p_1, p_2, \dots, p_n$。第 $i$ 个点 $p_i$ 的坐标为 $(x_i, y_i)$，权重为 $w_i$。

考虑一个参数为 $(a, b, c)$ 的查询，令 $S(a, b) = \{p_i \mid x_i \le a \land y_i \le b\}$。该查询表示：“是否存在一个 $S$ 的子集 $T$（$T \subseteq S$），使得 $(\sum_{p_i \in T} w_i) \pmod n = c$？”

令 $\text{query}(a, b, c) = \text{True/False}$ 为参数为 $(a, b, c)$ 的查询结果。你需要回答所有可能的查询。无需输出 $O(n^3)$ 行结果，你只需要计算以下值：

$$ans = \left( \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}] \right) \pmod{2^{64}}$$

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 5 \times 10^5$)，表示点的数量。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i, y_i$ 和 $w_i$ ($1 \le x_i, y_i, w_i \le n$)，描述第 $i$ 个点。注意，两个点可能位于相同的位置。

保证所有 $x_i, y_i$ 和 $w_i$ 的值均从其对应范围内的整数中均匀随机选择。随机性条件不适用于样例测试，但你的程序必须通过样例。

输出格式

输出一行，包含一个整数，表示 $ans$ 的值。

样例

样例输入 1

3
1 2 2
2 3 1
3 1 3

样例输出 1

75

样例输入 2

5
1 1 4
5 1 4
2 3 3
1 4 1
2 5 2

样例输出 2

1935