L. Appending LIS
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For an integer array $$$b$$$ and a given integer $$$k$$$, define $$$S(b)$$$ as follows. Perform exactly $$$k$$$ operations; in each operation, compute the length of the longest strictly increasing subsequence$$$^{\text{∗}}$$$ (LIS) of the current array $$$b$$$ and append this value to the end of $$$b$$$. Each operation acts on the array obtained from the previous ones. After the $$$k$$$ operations, $$$S(b)$$$ is the sum of all elements of the resulting array.

You are given an integer array $$$a$$$ of length $$$n$$$ and the integer $$$k$$$. For each $$$i$$$ from $$$1$$$ to $$$n$$$, compute $$$S(a[1..i])$$$, where $$$a[1..i]$$$ denotes the prefix $$$a_1, a_2, \ldots, a_i$$$. Each prefix is processed independently: the operations performed while computing $$$S(a[1..i])$$$ do not affect any other prefix.

$$$^{\text{∗}}$$$A subsequence is obtained from an array by deleting zero or more elements without changing the order of the remaining ones; it is strictly increasing if each of its elements is strictly greater than the previous one.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — the length of the array and the number of operations.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of the array.

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

Output

For each test case, output $$$n$$$ integers on a single line — the values $$$S(a[1..1]), S(a[1..2]), \ldots, S(a[1..n])$$$.

Example
Input
3
3 2
1 3 0
3 10
1 1 1
5 1
2 1 -1 3 2
Output
3 8 8
11 12 13
3 4 3 7 9
Note

In the first test case, $$$a = [1, 3, 0]$$$ and $$$k = 2$$$. Each prefix is processed independently.

  • Prefix $$$[1]$$$: the LIS has length $$$1$$$, so we append $$$1$$$, giving $$$[1, 1]$$$. The LIS is still $$$1$$$ (the two equal values $$$1$$$ cannot both belong to a strictly increasing subsequence), so we append $$$1$$$ again, giving $$$[1, 1, 1]$$$. The sum is $$$1 + 1 + 1 = 3$$$.
  • Prefix $$$[1, 3]$$$: the LIS has length $$$2$$$, so we append $$$2$$$, giving $$$[1, 3, 2]$$$. The LIS is still $$$2$$$, so we append $$$2$$$ again, giving $$$[1, 3, 2, 2]$$$. The sum is $$$1 + 3 + 2 + 2 = 8$$$.
  • Prefix $$$[1, 3, 0]$$$: the LIS has length $$$2$$$, so we append $$$2$$$, giving $$$[1, 3, 0, 2]$$$. The LIS is still $$$2$$$, so we append $$$2$$$ again, giving $$$[1, 3, 0, 2, 2]$$$. The sum is $$$1 + 3 + 0 + 2 + 2 = 8$$$.

So the answer for the first test case is $$$3\ 8\ 8$$$.