CF1614B.Divan and a New Project

The company "Divan's Sofas" is planning to build $n + 1$ different buildings on a coordinate line so that:

• the coordinate of each building is an integer number;
• no two buildings stand at the same point.

Let $x_i$ be the coordinate of the $i$-th building. To get from the building $i$ to the building $j$, Divan spends $|x_i - x_j|$ minutes, where $|y|$ is the absolute value of $y$.

All buildings that Divan is going to build can be numbered from $0$ to $n$. The businessman will live in the building $0$, the new headquarters of "Divan's Sofas". In the first ten years after construction Divan will visit the $i$-th building $a_i$ times, each time spending $2 \cdot |x_0-x_i|$ minutes for walking.

Divan asks you to choose the coordinates for all $n + 1$ buildings so that over the next ten years the businessman will spend as little time for walking as possible.

公司“Divan’s Sofas”计划在一条数轴上建造 $n + 1$ 座互不相同的建筑，满足以下条件：

• 每座建筑的坐标均为整数；
• 任意两座建筑不能位于同一点。

设第 $i$ 座建筑的坐标为 $x_i$。从建筑 $i$ 到建筑 $j$，Divan 需花费 $|x_i - x_j|$ 分钟，其中 $|y|$ 表示 $y$ 的绝对值。

Divan 计划建造的所有建筑编号为 $0$ 至 $n$。商人将居住在编号为 $0$ 的建筑中，即“Divan’s Sofas”的新总部。在建成后最初的十年间，Divan 将访问第 $i$ 座建筑 $a_i$ 次，每次往返均需步行 $2 \cdot |x_0 - x_i|$ 分钟。

Divan 请你为全部 $n + 1$ 座建筑选定坐标，使得未来十年内商人步行所花费的总时间最少。

Each test contains several test cases. The first line contains one integer number $t$ ($1 \le t \le 10^3$) — the number of test cases.

The first line of each case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of buildings that "Divan's Sofas" is going to build, apart from the headquarters.

The second line contains the sequence $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$), where $a_i$ is the number of visits to the $i$-th building.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示“Divan's Sofas”公司除总部外计划建造的楼栋数量。

第二行包含一个序列 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^6$），其中 $a_i$ 表示第 $i$ 栋楼的访问次数。

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

For each test case, on the first line print the number $T$ — the minimum time Divan will spend walking.

On the second line print the sequence $x_0, x_1, \ldots, x_n$ of $n + 1$ integers, where $x_i$ ($-10^6 \le x_i \le 10^6$) is the selected coordinate of the $i$-th building. It can be shown that an optimal answer exists with coordinates not exceeding $10^6$.

If there are multiple answers, print any of them.

对于每个测试用例，在第一行输出数字 $T$ —— Divan 行走所需的最少时间。

在第二行输出由 $n + 1$ 个整数组成的序列 $x_0, x_1, \ldots, x_n$，其中 $x_i$（$-10^6 \le x_i \le 10^6$）表示第 $i$ 座建筑物所选定的坐标。可以证明：存在一个最优解，其坐标值均不超过 $10^6$。

若存在多个答案，输出任意一个即可。

Let's look at the first example.

Divan will visit the first building $a_1 = 1$ times, the second $a_2 = 2$ times and the third $a_3 = 3$ times. Then one of the optimal solution will be as follows:

1. the headquarters is located in $x_0 = 2$;
2. $x_1 = 4$: Divan will spend $2 \cdot |x_0-x_1| \cdot a_1 = 2 \cdot |2-4| \cdot 1 = 4$ minutes walking to the first building;
3. $x_2 = 1$: Divan will spend $2 \cdot |x_0-x_2| \cdot a_2 = 2 \cdot |2-1| \cdot 2 = 4$ minutes walking to the second building;
4. $x_3 = 3$: Divan will spend $2 \cdot |x_0-x_3| \cdot a_3 = 2 \cdot |2-3| \cdot 3 = 6$ minutes walking to the third building.

In total, Divan will spend $4 + 4 + 6 = 14$ minutes. It can be shown that it is impossible to arrange buildings so that the businessman spends less time.

Among others, $x = [1, 3, 2, 0]$, $x = [-5, -3, -6, -4]$ are also correct answers for the first example.

我们来看第一个例子。

Divan 将分别访问第一栋楼 $a_1 = 1$ 次、第二栋楼 $a_2 = 2$ 次、第三栋楼 $a_3 = 3$ 次。此时，一种最优方案如下：

1. 总部设在 $x_0 = 2$；
2. $x_1 = 4$：Divan 前往第一栋楼需花费 $2 \cdot |x_0-x_1| \cdot a_1 = 2 \cdot |2-4| \cdot 1 = 4$ 分钟；
3. $x_2 = 1$：Divan 前往第二栋楼需花费 $2 \cdot |x_0-x_2| \cdot a_2 = 2 \cdot |2-1| \cdot 2 = 4$ 分钟；
4. $x_3 = 3$：Divan 前往第三栋楼需花费 $2 \cdot |x_0-x_3| \cdot a_3 = 2 \cdot |2-3| \cdot 3 = 6$ 分钟。

总计，Divan 将花费 $4 + 4 + 6 = 14$ 分钟。可以证明，不存在其他建筑位置安排方式能使该商人花费更少时间。

此外，对于第一个例子，$x = [1, 3, 2, 0]$、$x = [-5, -3, -6, -4]$ 等也是正确的答案。