You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小 I 并不会出题。小 I 把一些数据结构相关的元素组合在一起便有了这道试题！

题目描述

小 I 给了你长度为 $n$ 的数列 $a_1,a_2,\dots,a_n$。对 $[n]$ 的 $2^n-1$ 个子集 $S$，计算 $f(S)=\sum_{x\in S}a_x$，得到 $2^n-1$ 个和。

你要求的是这 $2^n-1$ 个和的中位数。很不可思议把！

输入格式

本题单点含有多组测试数据。

第一行一个正整数表示 $T$。

对于每组数据，第一行一个正整数 $n$，接下来 $n$ 个正整数表示 $a_i$。

输出格式

每组数据，一行一个正整数表示答案。

测试样例

样例解释

对于样例 $1$，第一组测试点 $f(\{1\})=1,f(\{2\})=1,f(\{1,2\})=2$，中位数为 $2$。

样例 ds2 内 $5$ 个测试点依次满足 $1,2,3,4,5$ 的限制。

样例 ds3 内 $5$ 个测试点依次满足 $6,7,8,9,10$ 的限制（可能不是极限样例）。

数据范围

对于所有测试点满足 $T\leq 500$。

• 特殊性质 A：对于单个测试点的 $a_i$ 完全相同。
• 特殊性质 B：保证单个测试点 $\sum a_i\leq 10^4$。