A12588 | 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.