核心共振

Problem Description

Wmc 最近制造出了 $n$ 个能量核心，并打算将它们放在一个平面上；第 $i$ 个能量核心的横坐标为 $x_i$ ，纵坐标为 $y_i$ ，且有一个能量强度 $a_i$ （3个参数均为整数）。 每个能量核心都在不间断地发出低频震荡波，每对能量核心发出的震荡波间都会产生共振能量：第 $i$ 与 $j$ 个能量核心间产生的共振能量为 $~f_{i,j}=(a_i+a_j) \cdot \max (\lvert x_i-x_j \rvert,\lvert y_i-y_j \rvert) $。 “整个矩阵产生的总共振能量”为“每对能量核心产生的共振能量”之和，即 $Ans=\sum\limits_{1 \leq i \leq j \leq n}f_{i,j}$ ；在放置能量核心前，Wmc 想先用程序计算这个值，以防过大的总共振能量震碎地球。

Input

第一行含一个正整数 $t ~ (1 \leq t \leq 10^3)$ ，表示共有多少组询问； 接下来 $t$ 组询问：

• 第一行含一个整数 $n ~ (1 \leq n \leq 2 \times 10^5)$ ，代表能量核心个数；
• 接下来的 $n$ 行，第 $i$ 行包含 $3$ 个整数，依次代表第 $i$ 个能量核心的横坐标 $x_i ~ (-10^9 \leq x_i \leq 10^9)$ ，纵坐标 $y_i ~ (-10^9 \leq y_i \leq 10^9)$ ，和能量强度 $a_i ~ (1 \leq a_{i,j} \leq 10^9)$ 。 保证 $\sum n \leq 10^6$ 。

Output

对每组询问，输出一个非负整数独占一行，表示所给出矩阵的总共振能量对 $10^9+7$ 取模后的结果。

Sample Input

6
2
1 1 500
1 2 2000
6
1 1 1
1 2 2
1 3 3
2 1 4
2 2 5
2 3 6
2
-1 0 50
-1 0 60
4
0 0 49
1 3 1
3 1 946
4 4 1522
3
-998244353 -998244353 1
998244353 998244353 2
998244353 998244853 3
1
0 0 7355608

Sample Output

2500
133
0
23286
975425351
0

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）