该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现在正在举行一场选举，有 $N$ 位候选人，编号为 $1, 2, \ldots, N$。目前已经有 $K$ 张选票，其中一些已经被计入。

到目前为止，第 $i$ 位候选人已经获得了 $A_i$ 票。

在所有选票被计完后，如果某位候选人的得票数比他们多的候选人数少于 $M$，那么该候选人将被当选。可能会有多位候选人同时当选。

对于每个候选人，求出他们需要从剩余的选票中获得的最少票数，以确保无论其他候选人获得多少票，他们都能当选。

具体来说，对于每个 $i = 1, 2, \ldots, N$，解决以下问题：

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

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

输入格式

• 第一行包含三个整数 $N$、$M$ 和 $K$。
• 第二行包含 $N$ 个整数，分别是 $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$。

数据范围

• $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$

样例

5 2 16
3 1 4 1 5

2 -1 1 -1 0

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：已知总共有 $14$ 票已经开票，剩下的选票为 $2$ 张。对于每位候选人，需要计算他们能够获得的最小额外选票数以确保当选。
  • 对于候选人 $1$，他需要额外获得 $2$ 票才能确保当选，因为即使他获得 $1$ 票，也不能确保他超过至少 $2$ 个候选人。
  • 对于候选人 $2$，无论剩下的 $2$ 张选票如何分配，他都无法确保当选，因此答案为 $-1$。
  • 对于候选人 $3$，他需要至少 $1$ 张额外选票才能确保当选。
  • 对于候选人 $4$，他无论如何也无法确保当选，因此答案为 $-1$。
  • 对于候选人 $5$，他已经得到了足够的票数，因此答案为 $0$。