题目描述

Farmer John 想举办另一场有 $n$ 头奶牛的锦标赛，第 $i$ 头奶牛的技能值为 $a_i$。重复以下过程，直到队列中只剩一头奶牛：

• 队首第一头奶牛与第二头奶牛战斗，技能值更高者获胜；若平局，第一头奶牛获胜。
• 获胜奶牛的技能值变为 $x+y$，其中 $x$ 是获胜者原技能值，$y$ 是失败者原技能值。
• 失败奶牛离开队列。

不过，为了贴近真实的 USACOW 比赛，一头奶牛最多可以作弊 $k$ 次。也就是说，即使它输掉一场战斗，Farmer John 也会把它当作获胜方处理：失败方技能值变为 $x+y$，获胜方离开队列。

对于奶牛 $i$，如果把它从原位置移除，并在不改变其它奶牛相对顺序的前提下插入到位置 $x$，且在没有其它奶牛作弊的情况下，它能成为锦标赛结束后唯一剩下的奶牛，则称位置 $x$ 对奶牛 $i$ 是好的。

请对队列中的每头奶牛，计算它的好位置数量。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行包含两个整数 $n,k$，分别表示奶牛数量和一头奶牛最多可以作弊的次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 头奶牛的好位置数量。

样例

7
2 0
2 1
2 0
1 1
3 1
1 1 3
3 0
2 1 1
3 1
1 3 1
4 1
1 2 1 3
7 2
1 3 3 17 39 3 12

2 0
1 1
2 2 3
2 0 0
3 3 2
4 4 4 4
4 6 6 7 7 5 7

样例说明

第一组测试数据中，技能值为 $2$ 的奶牛无论放在哪都能获胜，另一头奶牛无论放在哪都会失败。

第二组测试数据中，两头奶牛都能在位置 $1$ 获胜，但不能在位置 $2$ 获胜，因此答案均为 $1$。

第三组测试数据中，以奶牛 $1$ 为例：若放在位置 $1$，它第一场获胜，技能值变为 $2$，之后可以作弊一次赢下第二场；若放在位置 $2$，它第一场需要作弊，但之后仍会输掉；若放在位置 $3$，它第一场需要作弊，随后没有更多比赛。

数据范围

• $1 \le t \le 10^4$
• $2 \le n \le 2\cdot 10^5$
• $0 \le k < n$
• $1 \le a_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1074 (Div. 4), Problem H - BattleCows 2