起初有一个与问题名称相关的传说,但现在只是一个正式的陈述。
您在 $$$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$$$ 进行排序;
- 将 $$$d_{k + 1}$$$ 作为结果。
如果有多个最佳答案,您可以打印其中任何一个。
输入
第一行包含单个整数 $$$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 < n$$$) — 点数和常数 $$$k$$$。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 < a_2 < \dots < a_n \le 10^9$$$) — 按升序排列的点。
保证 $$$\sum{n}$$$ 不超过 $$$2 \cdot 10^5$$$。
输出
打印 $$$T$$$ 整数 - 对应点 $$$x$$$ 具有最小可能值 $$$f_k(x)$$$。如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
3 3 2 1 2 5 2 1 1 1000000000 1 0 4
输出 #1
3 500000000 4