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.

起初，这个问题的名称背后有一个传说，但现在它仅仅是一个形式化的陈述。

你被给定了 $OX$ 轴上的 $n$ 个点 $a_1, a_2, \dots, a_n$。现在，你需要在 $OX$ 轴上找出一个整数点 $x$，使得函数 $f_k(x)$ 的值尽可能小。

函数 $f_k(x)$ 的定义如下：

• 构造一个距离列表 $d_1, d_2, \dots, d_n$，其中 $d_i = |a_i - x|$（即 $a_i$ 与 $x$ 之间的距离）；
• 将列表 $d$ 按非降序（即升序）排序；
• 取排序后列表中的第 $k + 1$ 个元素 $d_{k + 1}$ 作为结果。

若存在多个最优解，你可以输出其中任意一个。

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 \lt 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 \lt a_2 \lt \dots \lt a_n \le 10^9$) — points in ascending order.

It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $T$（$1 \le T \le 2 \cdot 10^5$），表示查询次数。接下来的 $2 \cdot T$ 行包含各查询的描述。所有查询相互独立。

每个查询的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \lt n$），分别表示点的数量和常数 $k$。

每个查询的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_1 \lt a_2 \lt \dots \lt a_n \le 10^9$），表示按升序排列的点。

保证所有查询的 $n$ 之和不超过 $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.

输出 $T$ 个整数——即使得 $f_k(x)$ 取得最小可能值的对应点 $x$。若存在多个答案，可任选其一输出。