F. Abushogi's Revenge (Hard 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, and so on. On a player's turn, they can repeatedly choose any non-empty wallet and take at least one dollar from it. A player's turn only ends immediately when the wallet they last took money from reaches exactly $$$0$$$ dollars.

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 the game ends before turn $$$k$$$, 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 turn number you are querying.

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
1 1 1 1
Output
8 0
9 1
1 1