说明

你有一堆三角形区域，它们铺满了一个无限的二维平面。该镶嵌的定义如下（参见图示以更好地理解）：

• 回忆欧拉公式指出，对于实数 $x$，有 $e^{ix}=\cos (x)+i\sin (x)$。首先，在复平面上对所有整数 $x, y$ 绘制顶点 $x + y \exp(\pi i / 3)$。
• 然后，对于上一步中每三个构成边长为 $1$ 的等边三角形的顶点，绘制构成其边界的边。此外，在三角形的中心绘制一个顶点，并从三角形中心到三个外部顶点各绘制一条边。

给定 $N$（$2\le N\le 2\cdot 10^5$）个输入点，每个点都严格位于某个区域内部（即不在任何顶点或边上）。对于任意一对输入点，定义它们之间的距离为：画一条从一个点到另一个点且不经过任何顶点的路径，所经过的最少边数。

输出所有输入点之间的 $N(N-1)/2$ 个两两距离之和。

输入格式

第一行包含 $T$（$T\ge 1$），表示独立测试用例的数量。每个测试用例的格式如下：

第一行包含 $N$。

接下来 $N$ 行，每行包含三个整数 $x$、$y$ 和 $z$（$0\le x, y < 10^6$，$0\le z < 12$），表示复平面上的点 $x + y \exp(\pi i / 3) + \epsilon \cdot \exp((1 + 2z)\pi i / 12)$（其中 $\epsilon$ 是一个很小的正数）。

保证所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含所有 $N(N-1)/2$ 个两两距离之和。

6
2
0 0 0
0 0 0
2
0 0 0
1 1 7
2
0 0 0
0 0 6
3
0 0 1
0 0 5
0 0 9
2
0 2 11
1 1 1
2
2 0 11
1 1 1

0
3
6
12
2
6

提示

第二个测试用例如下所示：

• 顶点 $x + y \exp(\pi i / 3)$ 用 $(x, y)$ 标记，其中 $x \in [-1, 2]$，$y \in [-1, 2]$。
• 在上述顶点以及每个等边三角形的中心顶点处绘制点。
• 包含 $(x, y, z) = (0, 0, 0)$ 的三角形区域用绿色高亮。
• 包含 $(x, y, z) = (1, 1, 7)$ 的三角形区域用蓝色高亮。注意 $15\pi / 12 = 225^{\circ}$。

绘制了一条从第一个区域到第二个区域的示例路径，该路径穿过了三条边。

:::align{center} :::

评分标准

• 输入 2-5：$N \le 10$，$0 \le x, y < 5$
• 输入 6-13：$N \le 10$
• 输入 14-21：$T = 1$

题目来源：Benjamin Qi

翻译由 DeepSeek 完成