D. Медизация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два положительных целых числа $$$n$$$ и $$$k$$$, а также массив $$$a$$$ из $$$n$$$ целых чисел.

При выполнении операции вы можете выбрать любой подмассив размера $$$k$$$ из $$$a$$$, а затем удалить его из массива, не меняя порядок других элементов. Более формально, пусть $$$(l, r)$$$ — это операция над подпорядком $$$a_l, a_{l+1}, \ldots, a_r$$$, такая что $$$r-l+1=k$$$, тогда выполнение этой операции означает замену $$$a$$$ на $$$[a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]$$$.

Например, если $$$a=[1,2,3,4,5]$$$ и мы выполним операцию $$$(3,5)$$$ над этим массивом, он станет $$$a=[1,2]$$$. Помимо того, операция $$$(2, 4)$$$ приведет к $$$a=[1,5]$$$, а операция $$$(1,3)$$$ приведет к $$$a=[4,5]$$$.

Вам нужно повторять операцию, пока длина $$$a$$$ больше $$$k$$$ (что означает $$$|a| \gt k$$$). Какова наибольшая возможная медиана$$$^\dagger$$$ всех оставшихся элементов массива $$$a$$$ после процесса?

$$$^\dagger$$$Медиана массива длины $$$n$$$ — это элемент, индекс которого равен $$$\left \lfloor (n+1)/2 \right \rfloor$$$ после сортировки элементов в неубывающем порядке. Например: $$$median([2,1,5,4,3]) = 3$$$, $$$median([5]) = 5$$$, и $$$median([6,8,2,4]) = 4$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, 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
Примечание

В первом наборе входных данных подмассив $$$(l, r)$$$ может быть либо $$$(1, 3)$$$, либо $$$(2, 4)$$$. Таким образом, два получаемых конечных массива — это $$$[3]$$$ и $$$[2]$$$. Первый имеет большую медиану ($$$3 > 2$$$), поэтому ответ — $$$3$$$.

Во втором наборе входных данных три получаемых конечных массива — это $$$[6, 4]$$$, $$$[3, 4]$$$ и $$$[3, 2]$$$. Их медианы равны $$$4$$$, $$$3$$$ и $$$2$$$ соответственно. Ответ — $$$4$$$.

В третьем наборе входных данных в конечном массиве остается только один элемент, и это может быть любой элемент начального массива. Наибольший из них — $$$9$$$, поэтому ответ — $$$9$$$.