CF1978D.Elections

伯兰德正在举行选举。有 $n$ 位候选人参加选举，编号从 $1$ 到 $n$。第 $i$ 位候选人有 $a_i$ 名支持者会投票给他。此外，还有 $c$ 名尚未决定支持哪位候选人的“未决定者”。未决定者会投票给编号最小的候选人。

获得最多票数的候选人将赢得选举，如果有多位候选人获得相同的最高票数，则编号最小的候选人获胜。

你觉得这场选举太无聊且可预测，于是你决定排除掉一些候选人。如果你不允许编号为 $i$ 的候选人参加选举，那么他的所有 $a_i$ 名支持者都会变成未决定者，并会投票给编号最小的候选人。

你很好奇，对于每个 $i$ 从 $1$ 到 $n$，最少需要排除多少名候选人，才能让编号为 $i$ 的候选人赢得选举。

每个测试包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 2 \cdot 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $c$（$1 \le n \le 2 \cdot 10^5$，$0 \le c \le 10^9$），分别表示候选人数和未决定者人数。

每组测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示每位候选人的支持者人数。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出 $n$ 个整数，第 $i$ 个数表示让编号为 $i$ 的候选人赢得选举所需排除的最少候选人数。

在第一个测试用例中：

• 如果所有候选人都允许参选，编号为 $1$ 的候选人将获得 $3$ 票（$1$ 名未决定者会投票给他），编号为 $2$ 的候选人获得 $0$ 票，编号为 $3$ 的候选人获得 $3$ 票。因此，编号为 $1$ 的候选人获胜（他与编号为 $3$ 的候选人票数相同，但编号更小），所以他的答案是 $0$。
• 如果不允许编号为 $1$ 的候选人参选，他的 $2$ 名支持者会变成未决定者。此时编号为 $2$ 的候选人获得 $3$ 票（$3$ 名未决定者会投票给他），编号为 $3$ 的候选人获得 $3$ 票。因此，编号为 $2$ 的候选人获胜（他与编号为 $3$ 的候选人票数相同，但编号更小），所以他的答案是 $1$。
• 如果不允许编号为 $1$ 和 $2$ 的候选人参选，编号为 $3$ 的候选人获胜，所以他的答案是 $2$。

在第二个测试用例中，只要不允许编号为 $2$ 的候选人参选，编号为 $1$ 的候选人就能获胜。

由 ChatGPT 4.1 翻译