读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：power.in

输出：power.out

题目描述

给定 $n$ 个整数坐标点 $x_1,\dots,x_n$，它们都位于数轴上。

对于某个整数 $s$，我们构造线段 $[s,x_1]$、$[s,x_2]$、$\dots$、$[s,x_n]$。注意，如果 $x_i < s$，那么线段为 $[x_i,s]$。线段 $[a,b]$ 覆盖所有整数点 $a,a+1,a+2,\dots,b$。

我们定义点 $p$ 的“幂”为有多少条线段与坐标为 $p$ 的点相交，用 $f_p$ 表示。

你的任务是，对于每个 $s \in \{x_1,\dots,x_n\}$，计算 $\sum\limits_{p=1}^{10^9}f_p$，即所有从 $1$ 到 $10^9$ 的整数点的 $f_p$ 之和。

例如，若初始坐标为 $[1,2,5,7,1]$，选择 $s=5$，则线段为：$[1,5]$、$[2,5]$、$[5,5]$、$[5,7]$、$[1,5]$。各点的幂为：$f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0$。它们的和为 $2+3+3+3+5+1+1=18$。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示点的数量。

第二行包含 $n$ 个整数 $x_1,x_2,\dots,x_n$（$1 \le x_i \le 10^9$），表示这些点的坐标。

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

输出格式

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示当 $s=x_i$ 时所有点幂的总和。

输入输出样例

3
3
1 4 3
5
1 2 5 7 1
4
1 10 100 1000

8 7 6
16 15 18 24 16
1111 1093 1093 2893

说明/提示

在第一个测试用例中，我们首先选择 $s=x_1=1$，则形成的线段为：$[1,1]$、$[1,4]$、$[1,3]$。

各点的幂为：$f_1=3, f_2=2, f_3=2, f_4=1, f_5=0,\dots$。所有点幂的和为 $3+2+2+1+0+\dots+0=8$。

然后选择 $s=x_2=4$，线段为：$[1,4]$、$[4,4]$、$[3,4]$，各点幂为 $f_1=1, f_2=1, f_3=2, f_4=3$。

最后选择 $s=x_3=3$，线段为：$[1,3]$、$[3,4]$、$[3,3]$，各点幂为 $f_1=1, f_2=1, f_3=3, f_4=1$。