给定 $$$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$$$。
你的任务是计算 \{x_1,\dots,x_n\}$$$ 中每个 $$$s \$$$\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$$$ 的所有点的幂之和。
示例
输入 #1
3 3 1 4 3 5 1 2 5 7 1 4 1 10 100 1000
输出 #1
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$$$。