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

Little C defines $f(i)$ as the prefix rank of $a_i$, where $f(i)$ is equal to the number of elements in array $a$ that are strictly greater than $a_i$, plus $1$.

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

In each operation, Little C chooses a positive integer $t \le n$ and increases the value of $a_t$ by $1$.

Little C wants to know, for each $1 \le i \le n$, what is the minimum number of operations required to satisfy $f(i) \le k \le g(i)$?

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

Input

The first line contains three integers $c, n, k$, where $c$ is the test case number. $c=0$ indicates that the test case is a sample.

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

Output

Output $n$ lines, each containing an integer, where the integer on the $i$-th line represents the minimum number of operations required to satisfy $f(i) \le k \le g(i)$.

Examples

Input 1

0 6 3
1 1 4 5 1 4

Output 1

3
3
0
2
3
0

Note 1

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

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

Input 2

See rank/rank2.in and rank/rank2.ans in the additional files.

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

Input 3

See rank/rank3.in and rank/rank3.ans in the additional files.

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

Constraints

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

Special Property A: Guaranteed that for all $1 \le i < n$, $a_i \ge a_{i+1}$.

Special Property B: Guaranteed that $k=1$.