AT_abc424_e [ABC424E] Cut in Half

有一个袋子里装有 $N$ 根木棒，每根木棒的长度分别为 $A_1, A_2, \ldots, A_N$。 你需要重复进行 $K$ 次如下操作： - 从袋子中取出任意一根最长的木棒，将其等分成两根相等长度的木棒，并将这两根新木棒放回袋中。 经过 $K$ 次操作后，袋子中共有 $N + K$ 根木棒。请你找出其中第 $X$ 长的木棒的长度。 共有 $T$ 组测试数据，请分别回答每组测试数据。

输入从标准输入读入，格式如下： > $T$ > $\mathrm{testcase}_1$ > $\mathrm{testcase}_2$ > $\vdots$ > $\mathrm{testcase}_T$ 第 $i$ 组测试数据 $\mathrm{testcase}_i$ 的格式如下： > $N\ K\ X$ > $A_1\ \ldots\ A_N$

输出共 $T$ 行。第 $i$ 行 $(1 \leq i \leq T)$ 输出第 $i$ 组测试数据的答案。 当且仅当你的输出的绝对误差或相对误差不超过 $10^{-9}$ 时，答案才会被认为是正确的。

### 样例解释 1 在第 $1$ 组测试数据中，初始袋子中有 $3$ 根木棒，长度分别为 $20, 30, 40$。操作过程如下： - 从袋子中取出长度为 $40$ 的木棒，将其分成两根长度为 $20$ 的木棒，并放回袋子中。此时袋子中的木棒长度为 $20, 20, 20, 30$。 - 从袋子中取出长度为 $30$ 的木棒，将其分成两根长度为 $15$ 的木棒，并放回袋子中。此时袋子中的木棒长度为 $15, 15, 20, 20, 20$。 - 从袋子中取出长度为 $20$ 的木棒，将其分成两根长度为 $10$ 的木棒，并放回袋子中。此时袋子中的木棒长度为 $10, 10, 15, 15, 20, 20$。 - 从袋子中取出长度为 $20$ 的木棒，将其分成两根长度为 $10$ 的木棒，并放回袋子中。此时袋子中的木棒长度为 $10, 10, 10, 10, 15, 15, 20$。 经过操作后，第 $5$ 长的木棒长度为 $10$。 ### 数据范围 - $1 \leq T \leq 10^5$ - 对于每组测试数据： - $1 \leq N \leq 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq K \leq 10^9$ - $1 \leq X \leq N + K$ - 所有测试数据中 $N$ 的总和不超过 $10^5$。 - 所有输入均为整数。 由 ChatGPT 5 翻译