说明

Yuki 有一个长度为 $n$ 的序列 $a$。

对于序列 $a$，Yuki 定义其「鱼鱼值」等于：

$$\sum_{i=1}^n \operatorname{mex}(\{a_1,\dots,a_i\})$$

即序列 $a$ 的所有非空前缀的 $\operatorname{mex}$ 之和。

Yuki 定义一次「大了」操作为：

• 选择一个不大于 $n$ 的正整数 $i$ 和一个非负整数 $v$，将 $a_i$ 的值修改为 $a_i+v$。

你需要对于每个不大于 $n$ 的非负整数 $k$ 求出，若 Yuki 进行恰好 $k$ 次「大了」操作，序列 $a$ 的「鱼鱼值」最大能达到多少。

本题中，一个序列的 $\operatorname{mex}$ 为该序列中未出现过的最小非负整数，例如：

• $\operatorname{mex}(\{1,2,3\})=0$；
• $\operatorname{mex}(\{0\})=1$；
• $\operatorname{mex}(\{1,0,2,4\})=3$；

特别地，当序列为空时，该序列的 $\operatorname{mex}$ 为 $0$。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 $c,t$，分别表示该测试点所属的子任务编号和测试数据组数。样例满足 $c=0$。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行包含一个整数 $n$。
• 第二行包含 $n$ 个整数 $a_1,\dots,a_n$。

输出格式

对于每组测试数据，输出一行，包含 $n+1$ 个整数；第 $k+1$ 个整数表示，若 Yuki 进行恰好 $k$ 次「大了」操作，序列 $a$ 的「鱼鱼值」所能达到的最大值。

0 3
4
2 0 0 9
5
0 1 0 2 4
7
4 0 9 8 1 3 8

3 7 7 7 7
11 14 15 15 15 15
9 9 9 9 9 9 9 9

提示

样例 1 解释

对于第 $1$ 组测试数据：

• 当 $k=0$ 时，序列 $a$ 的「鱼鱼值」为 $0+1+1+1=3$；
• 当 $k=1$ 时，可以将 $a_3$ 的值修改为 $1$，此时序列 $a$ 的「鱼鱼值」为 $0+1+3+3=7$。

对于第 $2$ 组测试数据：

• 当 $k=0$ 时，序列 $a$ 的「鱼鱼值」为 $1+2+2+3+3=11$；
• 当 $k=1$ 时，可以将 $a_3$ 的值修改为 $3$，此时序列 $a$ 的「鱼鱼值」为 $1+2+2+4+5=14$；
• 当 $k=2$ 时，可以将 $a_3$ 和 $a_4$ 的值分别修改为 $2$ 和 $3$，此时序列 $a$ 的「鱼鱼值」为 $1+2+3+4+5=15$。

数据范围

设 $\sum n$ 表示单个测试点中 $n$ 的和，$\sum n^3$ 表示单个测试点中 $n^3$ 的和。

对于所有测试数据，均有：

• $1 \le t \le 10^5$；
• $1 \le n \le 500$，$\sum n^3 \le 500^3$；
• 对于所有 $1\le i \le n$，均有 $0 \le a_i \le 10^9$。

本题采用捆绑测试。

• Subtask 1（13 points）：$n \le 5$，$\sum n \le 20$。
• Subtask 2（17 points）：$n \le 16$，$\sum n \le 20$。
• Subtask 3（27 points）：$n \le 100$，$\sum n^3 \le 100^3$。
• Subtask 4（7 points）：保证序列 $a$ 是 $0$ 到 $n-1$ 的排列。
• Subtask 5（15 points）：保证序列 $a$ 单调不降。
• Subtask 6（21 points）：无特殊限制。