CF1175C Electrification

At first, there was a legend related to the name of the problem, but now it's just a formal statement. You are given $ n $ points $ a_1, a_2, \dots, a_n $ on the $ OX $ axis. Now you are asked to find such an integer point $ x $ on $ OX $ axis that $ f_k(x) $ is minimal possible. The function $ f_k(x) $ can be described in the following way: - form a list of distances $ d_1, d_2, \dots, d_n $ where $ d_i = |a_i - x| $ (distance between $ a_i $ and $ x $ ); - sort list $ d $ in non-descending order; - take $ d_{k + 1} $ as a result. If there are multiple optimal answers you can print any of them.

The first line contains single integer $ T $ ( $ 1 \le T \le 2 \cdot 10^5 $ ) — number of queries. Next $ 2 \cdot T $ lines contain descriptions of queries. All queries are independent. The first line of each query contains two integers $ n $ , $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 0 \le k < n $ ) — the number of points and constant $ k $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_1 < a_2 < \dots < a_n \le 10^9 $ ) — points in ascending order. It's guaranteed that $ \sum{n} $ doesn't exceed $ 2 \cdot 10^5 $ .

Print $ T $ integers — corresponding points $ x $ which have minimal possible value of $ f_k(x) $ . If there are multiple answers you can print any of them.