E. Abushogi's Revenge (Mid version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since MrMoon didn't mention abushogi in the editorial last time, he decided to take his revenge.

To settle the score, abushogi and void decided to play a game.There are $$$n$$$ wallets of Moons lined up on a table.

The $$$i$$$-th wallet initially contains $$$a_i$$$ dollars. The game is played in turns, with abushogi taking the first turn (Turn 1), void taking Turn 2, abushogi taking Turn 3, and so on.

On a player's turn, they choose exactly one available wallet on the table, take all the money inside it, and their turn immediately ends. The chosen wallet is then removed from the table.

Both players play optimally to maximize their own total amount of money. Given the initial amounts in the wallets, you need to determine the exact amount of money abushogi and void will each have at the end of turn $$$k$$$. If all wallets are taken before turn $$$k$$$, the game ends early, and you should output their final scores.

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 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — the number of wallets and the requested turn number.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial amount of dollars in each wallet.

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 two integers: the amount of money abushogi has, and the amount of money void has, respectively, at the end of turn $$$k$$$.

Example
Input
3
3 1
5 2 3
3 3
5 2 3
4 2
10 10 10 10
Output
5 0
7 3
10 10
Note

In the first test case, $$$k=1$$$. Abushogi takes the first turn. To maximize his money, he chooses the wallet with $$$5$$$ dollars. Void hasn't played yet. The scores are $$$5$$$ and $$$0$$$.

In the second test case, $$$k=3$$$. Abushogi takes the $$$5$$$, void takes the $$$3$$$, and abushogi takes the $$$2$$$. Total scores are $$$7$$$ and $$$3$$$.