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 翻译