dp

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,a[500009],o;
int sp[500009];
bool gt(int x){
for(int i = 0; i <= o; i ++)
sp[i] = 0;
for(int i = 1; i <= n; i ++){
int p = i % k == 0 ? k : i % k;
sp[p] = max(sp[p],sp[p - 1] + (a[i] >= x));
}
int p = n % k == 0 ? k : n % k;
return sp[p] * 2 > o;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&k);
o = n;
while(o > k)
o -= k;
for(int i = 1; i <= n; i ++){
scanf("%d",&a[i]);
}
int l = 1,r = 1e9 + 7;
while(l + 1 < r){
int mid = (l + r) >> 1;
if(gt(mid))
l = mid;
else
r = mid;
}
printf("%d\n",l);
}