{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eIn computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a min heap, for any given node $C$, if $P$ is a parent node of $C$, then the key(the value) of $P$ is less than or equal to the key of $C$. The node at the ``top\u0027\u0027 of the heap(with no parents) is called the root node.\u003cbr\u003e\u003cbr\u003eUsually, we may store a heap of size $n$ in an array $h_1,h_2,\\dots,h_n$, where $h_i$ denotes the key of the $i$-th node. The root node is the $1$-th node, and the parent of the $i(2\\leq i\\leq n)$-th node is the $\\lfloor\\frac{i}{2}\\rfloor$-th node.\u003cbr\u003e\u003cbr\u003eSunset and Elephant is playing a game on a min heap. The two players move in turns, and Sunset moves first. In each move, the current player selects a node which has no children, adds its key to this player\u0027s score and removes the node from the heap.\u003cbr\u003e\u003cbr\u003eThe game ends when the heap is empty. Both players want to maximize their scores and will play optimally. Please write a program to figure out the final result of the game.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer $T(1\\leq T\\leq 10000)$, denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eIn each test case, there is one integer $n(1\\leq n\\leq 100000)$ in the first line, denoting the number of nodes.\u003cbr\u003e\u003cbr\u003eIn the second line, there are $n$ integers $h_1,h_2,...,h_n(1\\leq h_i\\leq 10^9,h_{\\lfloor\\frac{i}{2}\\rfloor}\\leq h_i)$, denoting the key of each node.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that $\\sum n\\leq 10^6$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print a single line containing two integers $S$ and $E$, denoting the final score of Sunset and Elephant."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n3\r\n1 2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}