题目描述

小 C 有一个长度为 $n$ 的数组 $a$。

小 C 定义，$f(i)$ 为 $a_i$ 的前排名，其中 $f(i)$ 等于数组 $a$ 中大于 $a_i$ 的元素个数加 $1$。

小 C 还定义，$g(i)$ 为 $a_i$ 的后排名，其中 $g(i)$ 等于数组 $a$ 中大于等于 $a_i$ 的元素个数。

每次操作，小 C 需要选择一个不大于 $n$ 的正整数 $t$，并将 $a_t$ 的值增加 $1$。

小 C 想知道，对于每一个 $1 \le i \le n$，想要使 $f(i) \le k \le g(i)$，最少需要进行多少次操作？

可以证明一定存在一种操作方案使得 $f(i) \le k \le g(i)$。

输入格式

第一行三个整数 $c,n,k$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

第二行 $n$ 个整数，表示给定的数组 $a$。

输出格式

共 $n$ 行，每行一个整数，其中第 $i$ 行的整数表示想要使 $f(i) \le k \le g(i)$ 所至少需要进行的操作数。

0 6 3
1 1 4 5 1 4

3
3
0
2
3
0

提示

【样例解释 #1】

当 $i=1$ 时，小 C 可以选择 $t=1$ 并进行 $3$ 次操作。此时 $f(i)=2$，$g(i)=4$，满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $3$ 次操作。

当 $i=4$ 时，小 C 可以选择 $t=3$ 进行 $1$ 次操作，再选择 $t=6$ 进行 $1$ 次操作。此时 $f(i)=1$，$g(i)=3$，满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $2$ 次操作。

【样例 #2】

见附加文件中的 rank/rank2.in 与 rank/rank2.ans。

该样例满足测试点 $7$ 的限制。

【样例 #3】

见附加文件中的 rank/rank3.in 与 rank/rank3.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

对于 $100\%$ 的数据，$1 \le k \le n \le 5 \times 10^5$，$1 \le a_i \le 10^9$。

特殊性质 A：保证对于所有的 $1 \le i \lt n$，都有 $a_i \ge a_{i+1}$。

特殊性质 B：保证 $k=1$。