Trò Chơi Bánh Kem

Bessie và Elsie phát hiện một hàng gồm $N$ chiếc bánh ($2\le N\le 5·{10}^5$, $N$ chẵn) với kích thước $a_1,a_2,\dots ,a_N$ ($1\le a_i\le {10}^9$).

Trò chơi diễn ra xen kẽ giữa hai người chơi:

• Lượt Bessie: Chồng hai chiếc bánh liền kề thành một chiếc bánh có kích thước bằng tổng.
• Lượt Elsie: Lấy chiếc bánh ở đầu trái hoặc đầu phải.

Khi chỉ còn một chiếc bánh, Bessie ăn nó và Elsie ăn tất cả bánh đã thu thập. Cả hai chơi tối ưu để tối đa hóa phần mình nhận được, Bessie đi trước.

Dữ liệu vào

• Dòng đầu: $T$ ($1\le T\le 10$) là số test case.
• Mỗi test case:
  • Dòng $1$: Số nguyên $N$.
  • Dòng $2$: $N$ số nguyên $a_1,a_2,\dots ,a_N$.
• Tổng $N$ qua tất cả test case không vượt quá ${10}^6$.

Dữ liệu ra

Với mỗi test case, in ra hai số nguyên $b$ và $e$ - lượng Bessie và Elsie nhận được khi cả hai chơi tối ưu.

Ràng buộc

• Test $2$: Tất cả $a_i$ bằng nhau
• Test $3$: $N\le 10$
• Test $4$-$7$: $N\le 5000$
• Test $8$-$11$: Không có ràng buộc thêm

Ví dụ