E. The supermarket queue
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A supermarket has two checkouts to collect the products purchased by its customers and, for that reason, there are always two queues, which, however, progress at different speeds, resulting in anger among some customers. Fed up with the situation, the supermarket has decided to implement an algorithm to determine which queue each customer should be placed in, taking into account the estimated time it takes to serve them at the checkout, so that the total time to serve all customers is as short as possible.

Input

There will be several test cases, represented by a number $$$C$$$ on the first line. For each test case, on a single line, the number of customers in total, $$$N$$$, is indicated first, followed by $$$N$$$ numbers indicating the time $$$T$$$ each one takes to be served.

  • $$$1 \leq C \leq 3000$$$
  • $$$1 \leq T \leq 8000$$$
  • $$$1 \leq N \leq 3000$$$
  • The sum of all times $$$T$$$ over all test cases will not exceed $$$8000$$$
  • The sum of $$$N$$$ over all test cases will not exceed $$$3000$$$
Output

For each test case it is necessary to indicate the time taken by the first and second cashier, respectively, to serve the customers assigned to each of them, so that the difference between the two times is as small as possible. If it does not take the same time, the second cashier will take the longest.

Example
Input
3
3 1 3 1
4 1 3 6 2
6 2 2 3 4 8 11
Output
2 3
6 6
15 15