CF2185H.BattleCows 2

Farmer John wants to host another tournament with $n$ cows, where the $i$-th cow has a skill level of $a_i$. The following process repeats until there is only one cow in the line.

• The first cow in the line fights the second cow in the line, and the cow with the higher skill level wins. If there is a tie, the first cow wins.
• The winning cow's skill level is set to $x + y$, where $x$ is the skill level of the winning cow and $y$ is the skill level of the losing cow.
• The losing cow leaves the line.

However, to maintain accuracy to the real USACOW competition, a cow is able to cheat up to $k$ times. This means that even if it loses the match, Farmer John will treat it as if the losing cow won the match, meaning that the losing cow's skill level will be set to $x + y$, where $x$ is the skill level of the winning cow and $y$ is the skill level of the losing cow, and the winning cow will leave the line.

A position $x$ is good for a cow $i$ if cow $i$ can be removed from its original position and inserted at index $x$ without changing the order of the other cows and be the only cow remaining in the line once the tournament has ended, assuming no other cow cheats.

For each cow in the line, calculate the number of good positions for that cow.

农夫约翰希望举办另一场有 $n$ 头奶牛参加的比赛，其中第 $i$ 头奶牛的技能值为 $a_i$。以下过程将不断重复，直到队伍中仅剩一头奶牛为止：

• 队伍中排在第一位的奶牛与排在第二位的奶牛进行对决，技能值更高的奶牛获胜；若技能值相等，则排在第一位的奶牛获胜。
• 获胜奶牛的新技能值被设为 $x + y$，其中 $x$ 为获胜奶牛原有的技能值，$y$ 为失败奶牛的技能值。
• 失败奶牛离开队伍。

然而，为了更真实地模拟真实的 USACOW 比赛，每头奶牛最多可作弊 $k$ 次。这意味着：即使某头奶牛在对决中失败，农夫约翰也会将其视为获胜者——即该失败奶牛的新技能值被设为 $x + y$（其中 $x$ 为原获胜奶牛的技能值，$y$ 为该奶牛自身的技能值），而原本应获胜的那头奶牛反而离开队伍。

若将奶牛 $i$ 从其原始位置移除，并插入到位置 $x$（其余奶牛的相对顺序保持不变），且在不依赖任何其他奶牛作弊的前提下，最终该奶牛能成为比赛中唯一剩余的奶牛，则称位置 $x$ 对奶牛 $i$ 是“好的”。

对队伍中的每一头奶牛，请计算其对应的“好位置”的数量。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $0 \leq k \lt n$) — the number of cows and the number of cheats a cow can use.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the skill levels of the cows.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each test case, output $n$ integers, where the $i$-th integer denotes the number of good positions for cow $i$.

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示奶牛 $i$ 的“好位置”的数量。

For the first test case, cow $2$ would lose no matter what it was positioned, and cow $1$ would win no matter where it was positioned.

For the second test case, both cows could win at position $1$, but could not win at position $2$, meaning that they each have $1$ good position.

For the third test case, let's look at cow $1$.

• If cow $1$ were at position $1$, then it would win its first match, making its skill level equal to $2$, and could cheat to win its second match.
• If cow $1$ were at position $2$, then it would have to cheat to win its first match, but would then lose its second match.
• If cow $1$ were at position $3$, then it would have to cheat to win its first match, and would have no more matches.

对于第一个测试用例，无论奶牛 $2$ 处于什么位置，它都会输；而奶牛 $1$ 无论处于什么位置，都会赢。

对于第二个测试用例，两头奶牛在位置 $1$ 均可获胜，但在位置 $2$ 均无法获胜，因此每头奶牛各有 $1$ 个好位置。

对于第三个测试用例，我们来分析奶牛 $1$：

• 若奶牛 $1$ 处于位置 $1$，则它将在第一场比赛中获胜，使其技能等级变为 $2$，并可作弊赢得第二场比赛；
• 若奶牛 $1$ 处于位置 $2$，则它必须作弊才能赢得第一场比赛，但随后将在第二场比赛中落败；
• 若奶牛 $1$ 处于位置 $3$，则它必须作弊才能赢得第一场比赛，且之后将不再有比赛。