Banker

Edek works at a bank counter, handling deposits into and withdrawals from customer accounts. Because the job can get tedious, Edek came up with his own way of processing deposits and withdrawals.

At the start of the day, Edek has an amount $S$ in the till, which he can use for payouts. When a customer comes to deposit money, Edek records the deposit amount in the system and puts the received cash (customers always bring the exact amount) into an envelope, which he places on top of a pile of envelopes from earlier deposits.

When a customer comes to withdraw an amount $X$, Edek proceeds as follows:

• If the pile has no envelopes, the money is paid from the till.
• If the amount to withdraw $X$ is smaller than the smallest amount among all the envelopes on the pile, Edek pays the entire amount $X$ from the till.
• Otherwise, Edek repeatedly takes the top envelope off the pile and uses it toward the payout, continuing until the full amount has been paid. If, after the full amount has been paid, some money is left in the last envelope he took, that leftover is put into the till. If Edek removes every envelope from the pile and the customer still has not received the full amount, the remaining part is paid from the till.

You may assume the till always holds enough money to perform the required operations.

Because this is a banking system, Edek does not want to make a mistake. Help him by writing a program that computes how much money should be in the till and how much should be in the envelopes remaining on the pile after all customer deposits and withdrawals have been processed.

The first line contains a single integer $T$ ($1 \le T \le 3$), the number of test cases. The test cases follow.

Each test case records all customer actions. Its first line contains two integers $n$ ($1 \le n \le 10^6$) and $S$ ($1 \le S \le 10^{12}$): the number of customer actions and the amount initially in the till at the start of the day. Each of the next $n$ lines describes one customer action as a single integer $x$ ($-10^6 \le x \le 10^6$, $x \neq 0$). A positive value is a deposit into an account; a negative value is a withdrawal from an account.

You may assume that while the actions are processed, the till never holds more than $10^{12}$.

For each test case, print one line with two integers separated by a single space: the amount left in the till after all customer actions have been processed, and the total amount in the envelopes remaining on the pile.