Med-imize
Description
Given two positive integers $n$ and $k$, and another array $a$ of $n$ integers.
In one operation, you can select any subarray of size $k$ of $a$, then remove it from the array without changing the order of other elements. More formally, let $(l, r)$ be an operation on subarray $a_l, a_{l+1}, \ldots, a_r$ such that $r-l+1=k$, then performing this operation means replacing $a$ with $[a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]$.
For example, if $a=[1,2,3,4,5]$ and we perform operation $(3,5)$ on this array, it will become $a=[1,2]$. Moreover, operation $(2, 4)$ results in $a=[1,5]$, and operation $(1,3)$ results in $a=[4,5]$.
You have to repeat the operation while the length of $a$ is greater than $k$ (which means $|a| \gt k$). What is the largest possible median$^\dagger$ of all remaining elements of the array $a$ after the process?
$^\dagger$The median of an array of length $n$ is the element whose index is $\left \lfloor (n+1)/2 \right \rfloor$ after we sort the elements in non-decreasing order. For example: $median([2,1,5,4,3]) = 3$, $median([5]) = 5$, and $median([6,8,2,4]) = 4$.
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 5 \cdot 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.
For each test case, print a single integer — the largest median possible after performing the operations.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 5 \cdot 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.
Output
For each test case, print a single integer — the largest median possible after performing the operations.
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
Note
In the first test case, you can select a subarray $(l, r)$ which can be either $(1, 3)$ or $(2, 4)$. Thus, two obtainable final arrays are $[3]$ and $[2]$. The former one has the larger median ($3 > 2$) so the answer is $3$.
In the second test case, three obtainable final arrays are $[6, 4]$, $[3, 4]$, and $[3, 2]$. Their medians are $4$, $3$, and $2$ respectively. The answer is $4$.
In the third test case, only one element is left in the final array and it can be any element of the initial array. The largest one among them is $9$, so the answer is $9$.