如何赢得选举

题目描述

正在举行一场有 $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$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

设 $C_i$ 为候选人 $i$ 需要从剩余选票中获得的最少额外票数，使得无论其他候选人如何获得选票，都能保证当选。用空格分隔输出 $C_1, C_2, \ldots, C_N$。

如果候选人 $i$ 已经确保当选，则令 $C_i = 0$。如果候选人 $i$ 无论如何都无法确保当选，则令 $C_i = -1$。

样例

5 2 16
3 1 4 1 5

2 -1 1 -1 0

目前已统计 $14$ 张选票，还剩 $2$ 张选票。

需要输出的 $C$ 为 $(2, -1, 1, -1, 0)$。例如：

候选人 $1$ 再获得 $2$ 张选票即可确保当选，而再获得 $1$ 张选票则不行。因此 $C_1 = 2$。

候选人 $2$ 即使再获得 $2$ 张选票也永远无法确保当选，因此 $C_2 = -1$。

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

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

数据范围

• $1 \le M \le N \le 2 \times 10^5$
• $1 \le K \le 10^{12}$
• $0 \le A_i \le 10^{12}$
• $\displaystyle{\sum_{i=1}^{N} A_i} \le K$
• 输入均为整数