Wmc 最近制造出了 $n$ 个能量核心，并打算将它们放在一个平面上；第 $i$ 个能量核心的横坐标为 $x_i$，纵坐标为 $y_i$，且有一个能量强度 $a_i$（3个参数均为整数）。

每个能量核心都在不间断地发出低频震荡波，每对能量核心发出的震荡波间都会产生共振能量：第 $i$ 与 $j$ 个能量核心间产生的共振能量为

$$f_{i,j} = (a_i+a_j) \cdot \max(|x_i-x_j|,|y_i-y_j|) $$

“整个矩阵产生的总共振能量”为“每对能量核心产生的共振能量”之和，即

$$Ans = \sum_{1 \leq i \leq j \leq n} f_{i,j}$$

在放置能量核心前，Wmc 想先用程序计算这个值，以防过大的总共振能量震碎地球。

输入格式

第一行含一个正整数 $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 \leq 10^9)$。

保证 $\sum n \leq 10^6$。

输出格式

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

样例

输入

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

输出

2500
133
0
23286
975425351
0