Yuki has a sequence $a$ of length $n$.

For the sequence $a$, Yuki defines its "fish-fish value" as:

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

That is, the sum of the $\operatorname{mex}$ of all non-empty prefixes of the sequence $a$.

Yuki defines a "larger" operation as follows:

• Choose a positive integer $i \le n$ and a non-negative integer $v$, and update the value of $a_i$ to $a_i+v$.

For every non-negative integer $k \le n$, you need to find the maximum possible "fish-fish value" of the sequence $a$ if Yuki performs exactly $k$ "larger" operations.

In this problem, the $\operatorname{mex}$ of a sequence is the smallest non-negative integer that does not appear in the sequence. For example:

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

Specifically, when the sequence is empty, its $\operatorname{mex}$ is $0$.

Input

This problem contains multiple test cases.

The first line of input contains two integers $c$ and $t$, representing the subtask ID and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case is then provided as follows:

• The first line contains an integer $n$.
• The second line contains $n$ integers $a_1,\dots,a_n$.

Output

For each test case, output a single line containing $n+1$ integers; the $(k+1)$-th integer represents the maximum possible "fish-fish value" of the sequence $a$ after performing exactly $k$ "larger" operations.

Examples

Input 1

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

Output 1

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

Note 1

For the first test case:

• When $k=0$, the "fish-fish value" of sequence $a$ is $0+1+1+1=3$.
• When $k=1$, we can change the value of $a_3$ to $1$. The "fish-fish value" of sequence $a$ becomes $0+1+3+3=7$.

For the second test case:

• When $k=0$, the "fish-fish value" of sequence $a$ is $1+2+2+3+3=11$.
• When $k=1$, we can change the value of $a_3$ to $3$. The "fish-fish value" of sequence $a$ becomes $1+2+2+4+5=14$.
• When $k=2$, we can change the values of $a_3$ and $a_4$ to $2$ and $3$ respectively. The "fish-fish value" of sequence $a$ becomes $1+2+3+4+5=15$.

Constraints

Let $\sum n$ denote the sum of $n$ in a single test point, and $\sum n^3$ denote the sum of $n^3$ in a single test point.

For all test cases:

• $1 \le t \le 10^5$;
• $1 \le n \le 500$, $\sum n^3 \le 500^3$;
• For all $1 \le i \le n$, $0 \le a_i \le 10^9$.

This problem uses bundled testing.

• 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): The sequence $a$ is guaranteed to be a permutation of $0$ to $n-1$.
• Subtask 5 (15 points): The sequence $a$ is guaranteed to be non-decreasing.
• Subtask 6 (21 points): No special restrictions.