C. Электрификация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поначалу у задачи была легенда, связанная с ее названием, но было решено оставить только формальное условие.

Вам заданы $$$n$$$ точек $$$a_1, a_2, \dots, a_n$$$ на оси $$$OX$$$. И теперь вам необходимо найти такую целочисленную точку $$$x$$$ (также на оси $$$OX$$$), что значение $$$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)$$$. Если существует несколько ответов — выведите любой из них.

Пример
Входные данные
3
3 2
1 2 5
2 1
1 1000000000
1 0
4
Выходные данные
3
500000000
4