伯兰正在举行选举。有 $$$n$$$ 名候选人参加选举,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 位候选人有 $$$a_i$$$ 粉丝为他投票。此外,还有$$$c$$$ 人尚未决定他们最喜欢的候选人,让我们称他们为未决定。尚未做出决定的人将投票给票数最少的候选人。
获得最多票数的候选人获胜,如果多个候选人获得相同的最大票数,则其中票数最少的候选人获胜。
您发现这些选举过于无聊和可预测,因此您决定将一些候选人排除在外。如果不允许编号$$$i$$$的候选人参加选举,他的所有$$$a_i$$$粉丝都会犹豫不决,并投票给编号最小的候选人。
您很好奇,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,需要从候选人编号 $$$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
5 3 1 2 0 3 2 3 0 10 5 3 5 4 3 2 1 4 5 3 10 7 1 6 0 2 2 2 3 3 3
输出 #1
0 1 2 1 0 0 1 2 3 4 1 0 2 3 1 1 2 0 4 5
注意
在第一个测试用例中:
- 如果允许所有候选人,则候选人编号$$$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$$$ 将获胜。