Yuki is a dimensional girl from another world!

She lives on a spaceship in an $n$-dimensional universe at coordinates $(v_1, \dots, v_n)$. Suddenly, her sensors show a black hole expanding at the origin of the universe: for every positive integer $i$, at the $i$-th second, if any of the spaceship's coordinates are less than or equal to $i$, Yuki and her spaceship will be consumed by the black hole!

To escape, Yuki needs to stay as far away from the black hole as possible: for every positive integer $i$, at the $(i-0.5)$-th second, if Yuki has not yet been consumed by the black hole, she must choose $k$ distinct dimensions $s_1, \dots, s_k$ and increase $v_{s_1}, \dots, v_{s_k}$ by $1$ each.

However, because the spaceship's dashboard is broken, Yuki does not know how much fuel remains. Therefore, she asks you to find, for each positive integer $k < n$, the maximum non-negative integer $x$ such that under the optimal strategy, Yuki has not been consumed by the black hole at the $x$-th second. It is easy to prove that such a non-negative integer $x$ exists.

Input

The first line contains two integers $c$ and $n$, where $c$ represents the test case number. $c=0$ indicates that this test case is a sample.

The second line contains $n$ integers $v_1, \dots, v_n$.

Output

Output a single line containing $n-1$ integers, where the $i$-th integer represents the answer for $k=i$.

Examples

Input 1

0 3
1 2 3

Output 1

1 3

Note 1

For the case $k=1$, Yuki can change the coordinates from $(1, 2, 3)$ to $(2, 2, 3)$ at the $0.5$-th second. It is easy to prove that Yuki will definitely be consumed by the black hole at the $2$-nd second, so the answer is $1$.

For the case $k=2$, Yuki can change the coordinates to $(2, 3, 3)$, $(3, 3, 4)$, and $(4, 4, 4)$ at the $0.5$, $1.5$, and $2.5$-th seconds, respectively. It is easy to prove that Yuki will definitely be consumed by the black hole at the $4$-th second, so the answer is $3$.

Input 2

See $\textit{universe/universe2.in}$ and $\textit{universe2.ans}$ in the provided files.

This sample satisfies the constraints of test case $3$.

Input 3

See $\textit{universe/universe3.in}$ and $\textit{universe3.ans}$ in the provided files.

This sample satisfies the constraints of test case $6$.

Input 4

See $\textit{universe/universe4.in}$ and $\textit{universe4.ans}$ in the provided files.

This sample satisfies the constraints of test case $9$.

Input 5

See $\textit{universe/universe5.in}$ and $\textit{universe5.ans}$ in the provided files.

This sample satisfies the constraints of test case $15$.

Input 6

See $\textit{universe/universe6.in}$ and $\textit{universe6.ans}$ in the provided files.

This sample satisfies the constraints of test case $20$.

Constraints

For all test data, it is guaranteed that:

• $2 \le n \le 10^6$;
• $1 \le v_i \le 10^9$.

Special Property: All $v_i$ are guaranteed to be equal.