题目描述

一场选举中有 $N$ 名候选人，编号为 $1, 2, \ldots, N$。共有 $K$ 张选票，其中一部分已经统计完毕。

到目前为止，候选人 $i$ 已获得 $A_i$ 张选票。

在所有选票统计完毕后，候选人 $i$（$1 \leq i \leq N$）当选的条件是：获得比他们票数多的候选人数量少于 $M$。可能会有多个候选人当选。

对于每个候选人，找出他们从剩余选票中需要的最少额外票数，以确保他们无论如何都能当选。

形式化地，对于每个 $i = 1,2,\ldots,N$，解决以下问题：

确定是否存在一个不超过 $K - \displaystyle{\sum_{i=1}^{N}} A_i$ 的非负整数 $X$，满足以下条件。如果存在，找出满足条件的最小整数。

• 如果候选人 $i$ 获得 $X$ 张额外选票，那么候选人 $i$ 将始终当选。

输入格式

第一行三个空格隔开的整数 $N$ $M$ $K$；

第二行 $N$ 个空格隔开的整数表示到目前为止候选人们已获得的选票。

输出格式

设 $C_i$ 是候选人 $i$ 从剩余选票中需要的最少额外票数，以确保他们无论如何都能当选。按顺序输出 $C_1, C_2, \ldots, C_N$，用空格隔开。

如果候选人 $i$ 已经确保当选，则设 $C_i = 0$。如果候选人 $i$ 在任何情况下都无法确保当选，则设 $C_i = -1$。

样例输入 1

5 2 16
3 1 4 1 5

样例输出 1

2 -1 1 -1 0

已统计了 $14$ 张选票，还剩下 $2$ 张。
要输出的 $C$ 是 $(2, -1, 1, -1, 0)$。例如：

• 候选人 $1$ 获得 $2$ 张额外选票即可确保当选，而获得 $1$ 张则不能。因此，$C_1 = 2$。
• 候选人 $2$ 即使获得 $2$ 张额外选票也无法确保当选，所以 $C_2 = -1$。

样例输入 2

12 1 570
81 62 17 5 5 86 15 7 79 26 6 28

样例输出 2

79 89 111 117 117 74 112 116 80 107 117 106

数据规模

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^{12}$
• $0 \leq A_i \leq 10^{12}$
• $\displaystyle{\sum_{i=1}^{N} A_i} \leq K$