题目描述

有 $n + 1$ 座的建筑，编号从 $0\sim n$。

有一个人从编号为 $0$ 的建筑出发， 分别要去编号为 $i$ 的建筑 $a_i$ 次。

设编号为 $i$ 的建筑坐标为 $x_i$， 这个人往返编号为 $i$ 的建筑一趟花费的时间为 $2 \times|x_i - x_0|$ 。

求如何安排这 $n + 1$ 座建筑的坐标， 使这个人在路上花费的总时间最小。

输入格式

输入第一行一个整数 $t$，表示有 $t$ 组数据。

每组数据第一行一个整数 $n$， 第二行 $n$ 个数， 分别表示 $a_1$ …… $a_n$。

输出格式

每组数据输出共两行，第一行一个整数，表示最小要花费的总时间。第二行 $n + 1$ 个整数， 表示使总时间花费最小的 $x_0$ …… $x_n$。如果有多组符合条件的解，输出任意一组即可。

说明/提示

对于 $100\%$ 的数据，$1 \le t \le 10^3$，$1 \le n \le 2 \cdot 10^5$，$\sum n \le 2 \cdot 10^5$，$0 \le a_i \le 10^6$，$-10^6 \le x_i \le 10^6$。

样例

4
3
1 2 3
5
3 8 10 6 1
5
1 1 1 1 1
1
0

14
2 4 1 3
78
1 -1 0 2 3 4
18
3 6 1 5 2 4
0
1 2