A. Алиса и Боб
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы и Боба есть мешок с $$$n$$$ шарами, на $$$i$$$-м шаре записано число $$$v_i$$$. Они играют в следующую игру: оба загадывают по целому числу (обозначим число, загаданное Алисой, как $$$a$$$, и число, загаданное Бобом, как $$$b$$$), после этого начинают доставать шары из мешка в произвольном порядке, пока мешок не опустеет. За каждый шар один балл получает тот, к чьему загаданному число ближе число на шаре, при этом при равенстве балл получает Алиса.

Например, если $$$a = 10$$$, $$$b = 30$$$, то

  • за шары с числами $$$10, 1, 7, 18, 20$$$ и многими другими баллы получает Алиса (обратите внимание, что она получит балл за шар с числом $$$20$$$);
  • за шары с числами $$$59, 25, 30, 21$$$ и многими другими баллы получает Боб.

Бобу заранее удалось узнать, какое число загадает Алиса. Помогите ему загадать свое число так, чтобы максимизировать количество полученных им баллов.

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

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

Каждый набор входных данных состоит из двух строк:

  • в первой строке заданы два целых числа $$$n$$$ и $$$a$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le a \le 10^9$$$) — количество шаров в мешке и число, загаданное Алисой, соответственно.
  • во второй строке заданы $$$n$$$ целых чисел $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_1 \le v_2 \le \dots \le v_n \le 10^9$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число $$$b$$$ ($$$0 \le b \le 2 \cdot 10^9$$$), которое должен загадать Боб, чтобы получить максимальное количество баллов. Если таких чисел несколько, вы можете вывести любое из них.

Пример
Входные данные
3
7 21
10 20 30 40 50 60 70
6 500
200 200 300 500 600 600
2 7
7 7
Выходные данные
35
333
1337
Примечание

В первом наборе входных данных, если Боб выберет число $$$35$$$, он получит $$$5$$$ очков — за шары $$$30, 40, 50, 60, 70$$$.

В третьем наборе входных данных Боб получит $$$0$$$ очков независимо от того, какое число выберет.