베시와 엘시는 일렬로 놓인 \(N\)개의 케이크를 발견했다. 왼쪽부터 케이크의 크기는 \(a_1,a_2,\ldots,a_N\)이다.

두 소는 모두 가능한 한 많은 케이크를 먹고 싶어 한다. 하지만 매우 교양 있는 소들이기 때문에, 케이크를 나누기 위한 게임을 하기로 했다. 두 소는 번갈아 차례를 진행하며, 각 차례에는 다음 중 하나를 수행한다.

1. 베시는 서로 인접한 케이크 두 개를 골라 쌓는다. 두 케이크는 크기의 합을 크기로 갖는 하나의 새로운 케이크가 된다.
2. 엘시는 가장 왼쪽 또는 가장 오른쪽의 케이크 하나를 골라 자신의 보관함에 넣는다.

케이크가 하나만 남으면 베시는 그 케이크를 먹고, 엘시는 자신의 보관함에 있는 모든 케이크를 먹는다. 두 소가 자신이 먹을 케이크의 양을 최대화하도록 최적으로 플레이하고 베시가 먼저 시작할 때, 각 소가 먹게 되는 케이크의 양을 구하여라.

입력

첫째 줄에 독립적인 테스트 케이스의 수 \(T\)가 주어진다. (\(1\le T\le 10\))

각 테스트 케이스의 첫째 줄에는 짝수 \(N\)이 주어진다. (\(2\le N\le 5\cdot 10^5\))

둘째 줄에는 케이크의 크기를 나타내는 \(N\)개의 정수 \(a_1,a_2,\ldots,a_N\)이 공백으로 구분되어 주어진다. (\(1\le a_i\le 10^9\))

한 입력에 포함된 모든 테스트 케이스의 \(N\)의 합은 \(10^6\) 이하이다.

출력

각 테스트 케이스마다 두 소가 최적으로 플레이했을 때 베시와 엘시가 먹게 되는 케이크의 양 \(b\)와 \(e\)를 공백으로 구분하여 출력한다.

예제 입력

2
4
40 30 20 10
4
10 20 30 40

예제 출력

60 40
60 40

첫 번째 테스트 케이스에서 최적으로 플레이하면 다음과 같이 진행된다.

1. 베시는 가운데의 케이크 두 개를 쌓는다. 케이크의 크기는 \([40,50,10]\)이 된다.
2. 엘시는 가장 왼쪽의 케이크를 먹는다. 남은 케이크의 크기는 \([50,10]\)이 된다.
3. 베시는 남은 케이크 두 개를 쌓는다.

베시는 크기 \(30+20+10=60\)만큼의 케이크를 먹고, 엘시는 크기 \(40\)만큼의 케이크를 먹는다.

두 번째 테스트 케이스는 첫 번째 테스트 케이스를 뒤집은 것이므로 답이 같다.

서브태스크

출처

USACO 2024 December Contest, Silver, Problem 1. Cake Game