题目描述

有 $n$ 根铁棒，其中第 $i$ 根铁棒的长度为 $a_i$。这 $n$ 根铁棒按照 $1,2,3,\dots,n$ 的顺序焊接在一起，形成一根非常长的铁棒体似使得顺序固定。焊接两个相邻的铁棒会产生一个焊点，总共有 $n-1$ 个焊点。

小 Q 需要将这根铁棒切割回 $n$ 根铁棒。每次他可以选择一根至少含有一个焊点的铁棒，并选择一个焊点将该铁棒从焊点处切成两段根铁棒，然后记得得到的两根铁棒的长度分别为 $l_1$ 和 $l_2$。这次切割的不平衡度定义为 $|l_1 - l_2|$，而切割的代价定义为 $\min\{l_1, l_2\} \times \lceil \log_2(l_1 + l_2) \rceil$。
请注意，$|x|$ 表示 $x$ 的绝对值，$\lceil \log_2(x) \rceil$ 表示不超过 $x$ 的最小的整数。

小 Q 希望这 $n-1$ 次切割的不平衡度 $b_1, b_2, \dots, b_{n-1}$ 满足 $b_1 \ge b_2 \ge \dots \ge b_{n-1}$，并且这 $n-1$ 次切割的总代价最小。你需要对每个 $i = 1, 2, \dots, n-1$ 计算第一次切割在第 $i$ 根铁棒和第 $i+1$ 根铁棒之间的焊点时的最小总代价，或者指出不可能切割出 $n$ 根铁棒。

输入格式

入的第一行包含一个整数 $T$ ($1 \le T \le 200$)，表示测试数据的组数。
对于每组测试数据：

第一行包含一个整数 $n$ ($2 \le n \le 420$)，表示铁棒的数量。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示铁棒的长度。

保证所有测试数据的总和不超过 $420$。

输出格式

对于每组测试数据，输出一行包含 $n-1$ 个整数，其中第 $i$ 个整数表示第一次切割在第 $i$ 根铁棒和第 $i+1$ 根铁棒之间的焊点时的总代价，或者输出 $-1$ 表示不可能切割出 $n$ 根铁棒。

输入输出样例 #1

输入 #1

3
3
8 9 7
3
1 5 9
3
3 1 4

输出 #1

68 75
24 -1
-1 -1