문제

Bessie and Elsie have discovered a row of $N$ cakes $(2 \leq N \leq 5\cdot 10^5, N \text{ even})$ cakes, with sizes $a_1,a_2,\dots,a_N$ in that order ($1\le a_i\le 10^9$).

Each cow wants to eat as much as possible. However, being very civilized cows, they decided to play a game to split it! The game proceeds with both cows alternating turns. Each turn consists of one of the following:

Bessie chooses two adjacent cakes and stacks them, creating a new cake with the sum of the sizes.Elsie chooses either the leftmost or rightmost cake and puts it in her stash.

When only one cake remains, Bessie eats it, and Elsie eats all cakes in her stash. If both cows play optimally to maximize the amount of cake they eat and Bessie plays first, how much cake will each cow eat?

입력

Each input consists of $T$ ($1\le T\le 10$) independent test cases. It is guaranteed that the sum of all $N$ within an input does not exceed $10^6$.

Each test case is formatted as follows. The first line contains $N$. The next line contains $N$ space-separated integers, $a_1,a_2,\ldots,a_N$.

출력

For each test case, output a line containing $b$ and $e$, representing the amounts of cake Bessie and Elsie respectively will consume if both cows play optimally.

예제 입력 1

2
4
40 30 20 10
4
10 20 30 40

예제 출력 1

60 40
60 40

점수

Input 2: All $a_i$ are equal.Input 3: $N\le 10$Inputs 4-7: $N\le 5000$Inputs 8-11: No additional constraints.