AT_abc424_e [ABC424E] Cut in Half

長さが $ A_1,\ldots,A_N $ の $ N $ 本の棒が袋に入っています。 あなたは次の操作を $ K $ 回繰り返します。 - 袋に入っている棒の中で最も長いものを $ 1 $ 本取り出し、二等分して、 $ 2 $ 本の棒を袋に戻す $ K $ 回の操作が終わった後、袋の中にある $ N+K $ 本の棒のうち、長い方から $ X $ 番目のものの長さを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{testcase}_1 $ $ \mathrm{testcase}_2 $ $ \vdots $ $ \mathrm{testcase}_T $ $ \mathrm{testcase}_i $ は $ i $ 番目のテストケースを表し、次の形式で与えられる。 > $ N $ $ K $ $ X $ $ A_1 $ $ \ldots $ $ A_N $

$ T $ 行出力せよ。 $ i $ 行目 $ (1 \leq i \leq T) $ には $ i $ 番目のテストケースに対する答えを出力せよ。 真の解との絶対誤差または相対誤差が $ 10^{-9} $ 以下のとき正解と判定される。

### Sample Explanation 1 $ 1 $ 番目のテストケースでは、最初、袋の中には長さが $ 20,30,40 $ の $ 3 $ 本の棒が入っています。操作は次のように進行します。 - 長さ $ 40 $ の棒を袋から取り出し、長さ $ 20 $ の棒 $ 2 $ 本を袋に戻す。袋の中の棒の長さは $ 20,20,20,30 $ となる。 - 長さ $ 30 $ の棒を袋から取り出し、長さ $ 15 $ の棒 $ 2 $ 本を袋に戻す。袋の中の棒の長さは $ 15,15,20,20,20 $ となる。 - 長さ $ 20 $ の棒を袋から取り出し、長さ $ 10 $ の棒 $ 2 $ 本を袋に戻す。袋の中の棒の長さは $ 10,10,15,15,20,20 $ となる。 - 長さ $ 20 $ の棒を袋から取り出し、長さ $ 10 $ の棒 $ 2 $ 本を袋に戻す。袋の中の棒の長さは $ 10,10,10,10,15,15,20 $ となる。 操作後に長い方から $ 5 $ 番目の棒の長さは $ 10 $ です。 ### Constraints - $ 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 $ を超えない - 入力は全て整数