Problem Description

Xiao C has an array $a$ of length $n$.

Xiao C defines $f(i)$ as the front rank of $a_i$, where $f(i)$ equals the number of elements in array $a$ that are greater than $a_i$, plus $1$.

Xiao C also defines $g(i)$ as the back rank of $a_i$, where $g(i)$ equals the number of elements in array $a$ that are greater than or equal to $a_i$.

In each operation, Xiao C needs to choose a positive integer $t$ not greater than $n$, and increase the value of $a_t$ by $1$.

Xiao C wants to know, for each $1 \le i \le n$, in order to make $f(i) \le k \le g(i)$ hold, what is the minimum number of operations needed?

It can be proven that there is always at least one sequence of operations that makes $f(i) \le k \le g(i)$.

Input Format

The first line contains three integers $c,n,k$, where $c$ indicates the test point ID. $c=0$ means this test point is the sample.

The second line contains $n$ integers, representing the given array $a$.

Output Format

Output $n$ lines in total, each containing one integer. The integer on line $i$ indicates the minimum number of operations needed to make $f(i) \le k \le g(i)$ hold.

0 6 3
1 1 4 5 1 4

3
3
0
2
3
0

Hint

Sample Explanation #1

When $i=1$, Xiao C can choose $t=1$ and perform $3$ operations. Then $f(i)=2$ and $g(i)=4$, satisfying $f(i) \le k \le g(i)$. It can be proven that Xiao C needs at least $3$ operations in this case.

When $i=4$, Xiao C can first choose $t=3$ and perform $1$ operation, then choose $t=6$ and perform $1$ operation. Then $f(i)=1$ and $g(i)=3$, satisfying $f(i) \le k \le g(i)$. It can be proven that Xiao C needs at least $2$ operations in this case.

Sample #2

See rank/rank2.in and rank/rank2.ans in the attachment.

This sample satisfies the constraints of test point $7$.

Sample #3

See rank/rank3.in and rank/rank3.ans in the attachment.

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

Constraints

For $100\%$ of the data, $1 \le k \le n \le 5 \times 10^5$, and $1 \le a_i \le 10^9$.

Special Property A: It is guaranteed that for all $1 \le i \lt n$, $a_i \ge a_{i+1}$ holds.

Special Property B: It is guaranteed that $k=1$.

Translated by ChatGPT 5