Farmer John 希望举办另一场有 $$$n$$$ 头牛的锦标赛,其中第 $$$i$$$ 头牛的技能水平为 $$$a_i$$$。重复以下过程,直到队列中只有一头牛为止。
- 队伍中的第一头牛与队伍中的第二头牛战斗,技能等级较高的牛获胜。如果平局,则第一头牛获胜。
- 获胜奶牛的技能等级设置为 $$$x + y$$$,其中 $$$x$$$ 是获胜奶牛的技能等级,$$$y$$$ 是失败奶牛的技能等级。
- 失败的牛离开队伍。
然而,为了保持真正的 USACOW 比赛的准确性,一头牛可以作弊多达 $$$k$$$ 次。这意味着即使输掉了比赛,Farmer John 也会将其视为失败的奶牛赢得了比赛,这意味着失败的奶牛的技能等级将被设置为 $$$x + y$$$,其中 $$$x$$$ 是获胜奶牛的技能等级,$$$y$$$ 是失败奶牛的技能等级,获胜的奶牛将离开队伍。
位置 $$$x$$$ 对于奶牛 $$$i$$$ 有好处,如果奶牛 $$$i$$$ 可以从其原始位置移除并插入到索引 $$$x$$$ 处 不改变其他牛的顺序 并且在比赛结束后成为队伍中唯一剩下的牛,假设没有其他牛作弊。
对于队列中的每头牛,计算该牛的好位置数。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \leq k \lt n$$$) — 奶牛的数量和奶牛可以使用的作弊数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 奶牛的技能水平。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数表示奶牛 $$$i$$$ 的好位置数。
示例
输入复制
72 02 12 01 13 11 1 33 02 1 13 11 3 14 11 2 1 37 21 3 3 17 39 3 12
输出复制
2 01 12 2 32 0 03 3 24 4 4 44 6 6 7 7 5 7
注意
对于第一个测试用例,牛 $$$2$$$ 无论其位置如何都会失败,而牛 $$$1$$$ 无论其位置在何处都会获胜。
对于第二个测试用例,两头牛都可以在位置 $$$1$$$ 获胜,但无法在位置 $$$2$$$ 获胜,这意味着它们各自都有 $$$1$$$ 好的位置。
对于第三个测试用例,让我们看一下奶牛 $$$1$$$。
- 如果牛 $$$1$$$ 处于位置 $$$1$$$,那么它将赢得第一场比赛,使其技能等级等于 $$$2$$$,并且可以作弊赢得第二场比赛。
- 如果牛 $$$1$$$ 位于 $$$2$$$ 位置,那么它必须作弊才能赢得第一场比赛,但随后会输掉第二场比赛。
- 如果牛 $$$1$$$ 处于位置 $$$3$$$,那么它必须作弊才能赢得第一场比赛,并且不会再有比赛。