AT_abc444_f [ABC444F] Half and Median

有 $N$ 根木棒，第 $i$ 根木棒的长度为 $A_i$。 你将进行 $M$ 次如下操作： - 选择一根长度至少为 $2$ 的木棒，设其长度为 $l$，将该木棒分成两根长度分别为 $\left\lfloor\frac{l}{2}\right\rfloor$ 和 $\left\lceil\frac{l}{2}\right\rceil$ 的木棒。 根据约束条件，可以证明一定能够进行 $M$ 次操作。 经过 $M$ 次操作后，将剩下 $N+M$ 根木棒。请你求出这些木棒长度可能的最大中位数。 本题包含 $T$ 组测试数据。 什么是中位数？当有 $N$ 个数时，$N+1$ 个数的中位数为将它们按照升序排序后的第 $1+\frac{N}{2}$ 个数。 例如，$(1,3,4,5,8)$ 的中位数为 $4$，而 $(2,2,2)$ 的中位数为 $2$。 注意，在本题中，按照约束条件，需要计算中位数的木棒数量总是奇数。

输入由标准输入给出，格式如下： > $T$ > $case_1$ > $case_2$ > $\vdots$ > $case_T$ 每个测试用例如下格式： > $N\ M\ A_1\ A_2\ \ldots\ A_N$

输出共 $T$ 行。第 $t$ 行输出第 $t$ 个测试用例的答案。

### 样例解释 1 在第一个测试用例中，如果你在第一次操作选择长度为 $14$ 的木棒，将其分成两根长度都是 $7$ 的木棒，此时你拥有长度为 $7,7,2,5,19,1$ 的六根木棒。接下来再选择长度为 $19$ 的木棒，将其分成两根长度分别为 $9,10$ 的木棒，此时你拥有长度为 $7,7,2,5,9,10,1$ 的七根木棒。在这种情况下，这些木棒长度的中位数为 $7$。 ### 数据范围 - $1 \leq T \leq 10^5$ - $1 \leq N \leq 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq M \leq \sum_{i=1}^N A_i - N$ - $N+M$ 是奇数 - 所有输入均为整数。 - 所有测试用例中 $N$ 的总和不超过 $10^5$。 由 ChatGPT 5 翻译