假设你和你的队友 Mixsx 将参加 Namomo 夏令营。Namomo 夏令营将持续 $n$ 天。我们将第 $i$ 天称为第 $i$ 天 ($1 \le i \le n$)。第 $i$ 天的费用为 $s_i$。

不幸的是，Namomo 夏令营的时间表与 Mixsx 的期末考试冲突了。Mixsx 在第 $L$ 天到第 $R$ 天之间每天都有期末考试。由于他的学校尚未公布 $L$ 和 $R$ 的确切值，我们假设每一对满足 $1 \le L \le R \le n$ 的整数对被选中的概率均为 $1/(n(n + 1)/2)$。他决定参加所有考试，因此在第 $L$ 天到第 $R$ 天缺席 Namomo 夏令营。在这种情况下，他的损失为 $\sum_{i=L}^R s_i$。

作为 Mixsx 的队友，你希望 Mixsx 放弃期末考试并回到 Namomo 夏令营。你可以在 $L$ 和 $R$ 公布之前准备 $k$ 个计划。在第 $i$ 个计划 ($1 \le i \le k$) 中，你可以在从第 $l_i$ 天到第 $r_i$ 天的每一天切断他学校的电力。只要 $l_i$ 和 $r_i$ 是满足 $1 \le l_i \le r_i \le n$ 的两个整数，你就可以选择它们的值。

一旦 $L$ 和 $R$ 公布，你可以选择一个计划 $x$ ($1 \le x \le k$)，使得 $L \le l_x \le r_x \le R$。那么 Mixsx 将在从第 $l_x$ 天到第 $r_x$ 天的每一天回到 Namomo 夏令营。在这种情况下，他的损失变为 $\sum_{i=L}^R s_i - \sum_{i=l_x}^{r_x} s_i$。你将选择一个使 Mixsx 损失最小化的计划。如果没有计划 $x$ 满足 $L \le l_x \le r_x \le R$，Mixsx 将正常参加期末考试，他的损失为 $\sum_{i=L}^R s_i$。

请计算如果你最优地选择 $k$ 个计划，Mixsx 的最小可能期望损失 $ans_k$。对于每个从 $1$ 到 $n(n + 1)/2$ 的 $k$，输出 $ans_k \cdot n(n + 1)/2$。

形式化地，给定一个包含 $n$ 个数字的列表 $s_i$ ($1 \le i \le n$)，定义损失函数 $C(L, R) = \sum_{i=L}^R s_i$。给定一个整数 $k$ ($1 \le k \le n(n+ 1)/2$)，你应该选择 $2k$ 个整数 $l_1, \dots, l_k, r_1, \dots, r_k$，满足对于所有 $1 \le i \le k$ 都有 $1 \le l_i \le r_i \le n$，使得

$$\sum_{1 \le L \le R \le n} \left[ C(L, R) - \max_{1 \le i \le k, L \le l_i \le r_i \le R} C(l_i, r_i) \right]$$

最小化。（如果不存在满足 $1 \le i \le k$ 且 $L \le l_i \le r_i \le R$ 的 $i$，则 $\max_{1 \le i \le k, L \le l_i \le r_i \le R} C(l_i, r_i)$ 定义为 $0$。）

输出对于每个 $k \in [1, n(n + 1)/2]$ 的最小化值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 9$)。第二行包含 $n$ 个空格分隔的整数 $s_i$ ($1 \le s_i \le 10^9$)。

输出格式

输出包含 $n(n + 1)/2$ 个整数，每行一个，即当 $k = 1, \dots, n(n + 1)/2$ 时，期望值乘以 $n(n + 1)/2$ 的结果。可以证明结果总是整数。

样例

输入 1

1
1

输出 1

0

输入 2

2
13 24

输出 2

26
13
0

输入 3

3
6 4 7

输出 3

33
21
12
8
4
0

说明

对于第一个测试用例，我们只需要考虑 $k = 1$ 的情况。我们只能选择 $l_1 = r_1 = 1$。那么期望损失为 $C(1, 1) - C(1, 1) = 0$，结果为 $0 \times 1 \times (2)/2 = 0$。

对于第三个测试用例，考虑 $k = 3$ 的情况。我们选择 $l_1 = r_1 = 1$，$l_2 = r_2 = 3$ 以及 $l_3 = 1, r_3 = 3$。期望损失为 $2$。结果为 $2 \times 6 = 12$。