H. BattleCows 2
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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

Example
Input
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
Output
2 0 
1 1 
2 2 3 
2 0 0 
3 3 2 
4 4 4 4 
4 6 6 7 7 5 7
Note

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.