Med-imize

时间限制：2 秒
空间限制：256 MB

给定两个正整数 $n$ 和 $k$，以及一个包含 $n$ 个整数的数组 $a$。

在一次操作中，你可以选择 $a$ 的任意一个大小为 $k$ 的子数组，然后将其从数组中删除，其余元素的顺序保持不变。更形式化地，设 $(l, r)$ 是对子数组 $a_l, a_{l+1}, \dots, a_r$ 的一个操作，满足 $r - l + 1 = k$，则执行该操作意味着将 $a$ 替换为 $[a_1, \dots, a_{l-1}, a_{r+1}, \dots, a_n]$。

例如，若 $a = [1, 2, 3, 4, 5]$，操作 $(3, 5)$ 会将数组变为 $[1, 2]$。操作 $(2, 4)$ 将得到 $[1, 5]$，操作 $(1, 3)$ 将得到 $[4, 5]$。

你需要不断重复这一操作，直到数组 $a$ 的长度大于 $k$ 的条件不再成立（即 $|a| \le k$）。在经过上述过程后，最终剩下的数组的最大可能中位数†是多少？

† 长度为 $m$ 的数组的中位数，是指将数组元素按非递减排序后，下标为 $\lfloor (m+1)/2 \rfloor$ 的元素。例如：$\operatorname{median}([2,1,5,4,3]) = 3$，$\operatorname{median}([5]) = 5$，$\operatorname{median}([6,8,2,4]) = 4$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试数据组数。

每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 5 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 数组 $a$。

保证所有测试数据的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数 —— 经过操作后能得到的最大中位数。

样例输入

5
4 3
3 9 9 2
5 3
3 2 5 6 4
7 1
5 9 2 6 5 4 6
8 2
7 1 2 6 8 3 4 5
4 5
3 4 5 6

样例输出

3
4
9
6
4
 

样例解释

• 第一个样例：可以选择的子数组为 $(1,3)$ 或 $(2,4)$，得到的最终数组分别为 $[3]$ 和 $[2]$。前者的中位数更大（$3 > 2$），故答案为 $3$。
• 第二个样例：三种可能的最终数组为 $[6,4]$、$[3,4]$ 和 $[3,2]$，其中位数分别为 $4$、$3$ 和 $2$。答案为 $4$。
• 第三个样例：最终只剩一个元素，它可以是由初始数组中任意一个元素变成。其中最大者为 $9$，故答案为 $9$。