Electrification

题意翻译

给长度为 $n$ 的单增序列 $a_1, a_2, \cdots, a_n$，定义 $f_k(x)$ 如下： - 令 $d_i=|a_i-x|$，然后将所有 $d_i$ 升序排序，得出$f_k(x)=d_{k+1}$ 你的任务是找一个 $x$ 使得 $f_k(x)$ 最小，输出任意一个答案即可。

题目描述

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.

输入输出样例

输入样例 #1

3
3 2
1 2 5
2 1
1 1000000000
1 0
4

输出样例 #1

3
500000000
4