题目描述

在王者荣耀这款游戏中，有一条分路叫做打野路，作为打野路中顶尖的两位英雄李白和李元芳今天迎来了最强野王之争！

李白和李元芳发现了一行N个野怪（2≤N≤5⋅10^5，N为偶数），野怪赏金依次为 a1,a2,…,aN（1≤ai≤10^9）。

李白和李元芳都想尽可能多的拿到奖金，但是作为拥有众多粉丝的偶像，他们还是进行了文明的对决，他们决定通过一个游戏来分配野怪，游戏在两个英雄之间轮流进行，每个回合两者进行一下操作

李白选择将两组相邻的野怪堆在一起形成一组新的野怪，赏金为两组野怪赏金之和

李元芳选择把最左边或者最右边的野怪藏起来

当只剩下一组野怪时候，李白会打掉他们从而收获奖金，而李元芳会打掉他所藏起来的所有野怪，如果两个人均采用最优策略最大化自己拿到的赏金，并且李白先进行操作，那么两位英雄最后拿到的赏金各是多少？

输入格式：

每个测试点包含 T（1≤T≤10）个独立的测试用例。输入保证一个测试点中的所有N之和不超过10^6。 每个测试用例的格式如下。第一行包含 N。下一行包含N个空格分隔的整数 a1,a2,…,aN。

输出格式：

对于每个测试用例，输出一行，包含b和e，两个人均采用最优策略最大化自己拿到的赏金，并且李白先进行操作，两位英雄最后拿到的赏金各是多少

输入样例：

2

4

40 30 20 10

4

10 20 30 40

输出样例：

60 40

60 40

测试点性质：

测试点 2：所有 ai相等。 测试点 3：N≤10。 测试点 4-7：N≤5000。 测试点 8-11：没有额外限制。