题目描述

有 $n$ 根铁棒，其中第 $i$ 根铁棒的长度为 $a_i$。这 $n$ 根铁棒按照 $1,2,3,...,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(y) \rceil$ 表示满足 $2^x \geq y$ 的最小整数 $x$。

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

输入格式

输入的第一行包含一个整数 $T (1 \leq T \leq 200)$，表示测试数据的组数。

对于每组测试数据：

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

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

输出格式

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

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

68 75
24 -1
-1 -1