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 想先用程序计算这个值，以防过大的总共振能量震碎地球。

第一行含一个正整数 $ 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 $ 。

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