AT_abc424_e [ABC424E] Cut in Half

There are $ N $ sticks in a bag, with lengths $ A_1,\ldots,A_N $ . You repeat the following operation $ K $ times. - Take out any one of the longest sticks in the bag, split it into two equal halves, and put the two sticks back into the bag. After $ K $ operations, among the $ N+K $ sticks in the bag, find the length of the $ X $ -th longest one. You are given $ T $ test cases; answer each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{testcase}_1 $ $ \mathrm{testcase}_2 $ $ \vdots $ $ \mathrm{testcase}_T $ $ \mathrm{testcase}_i $ represents the $ i $ -th test case and is given in the following format: > $ N $ $ K $ $ X $ $ A_1 $ $ \ldots $ $ A_N $

Print $ T $ lines. In the $ i $ -th line $ (1 \leq i \leq T) $ , output the answer for the $ i $ -th test case. Your answer will be judged correct if the absolute or relative error is at most $ 10^{-9} $ .

### Sample Explanation 1 In the $ 1 $ -st test case, initially the bag contains $ 3 $ sticks of lengths $ 20,30,40 $ . The operations proceed as follows. - Take out the stick of length $ 40 $ from the bag, split it into two sticks of length $ 20 $ , and put them back. The stick lengths in the bag become $ 20,20,20,30 $ . - Take out the stick of length $ 30 $ from the bag, split it into two sticks of length $ 15 $ , and put them back. The stick lengths in the bag become $ 15,15,20,20,20 $ . - Take out a stick of length $ 20 $ from the bag, split it into two sticks of length $ 10 $ , and put them back. The stick lengths in the bag become $ 10,10,15,15,20,20 $ . - Take out a stick of length $ 20 $ from the bag, split it into two sticks of length $ 10 $ , and put them back. The stick lengths in the bag become $ 10,10,10,10,15,15,20 $ . After the operations, the $ 5 $ -th longest stick has length $ 10 $ . ### Constraints - $ 1 \leq T \leq 10^5 $ - For each test case: - $ 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 $ - The sum of $ N $ over all test cases does not exceed $ 10^5 $ . - All input values are integers.