Alice 和 Bob 有一个袋子,里面装着 $$$n$$$ 弹珠,第 $$$i$$$ 弹珠上写着整数 $$$v_i$$$。他们玩以下游戏:首先,每个玩家选择一个整数(让我们将 Alice 选择的整数表示为 $$$a$$$,将 Bob 选择的整数表示为 $$$b$$$)。之后,他们开始以任意顺序从袋子中取出弹珠,直到袋子空为止。对于每个球,分数将指向所选整数更接近弹珠上的整数的那个球; 如果平局,爱丽丝得分.
例如,如果 $$$a = 10$$$,$$$b = 30$$$,则
- 对于整数 $$$10, 1, 7, 18, 20$$$ 和许多其他的弹珠,爱丽丝获得分数(请注意,她将获得弹珠 $$$20$$$ 的分数);
- 对于整数 $$$59、25、30、21$$$ 和许多其他整数的大理石,Bob 获得了分数。
Bob 已经设法提前找出 Alice 会选择哪个整数。帮助他选择整数,使他获得的分数最大化。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含两个整数 $$$n$$$ 和 $$$a$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le a \le 10^9$$$)——分别是袋子里弹珠的数量和 Alice 选择的数量。
- 第二行包含 $$$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$$$),Bob 应选择该整数来最大化他收到的点数。如果有多个这样的数字,则可以输出其中任何一个。
示例
输入复制
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
注意
在第一个测试用例中,如果 Bob 选择 $$$35$$$,他会因为弹珠 $$$30, 40, 50, 60, 70$$$ 获得 $$$5$$$ 点。
在第三个测试用例中,无论 Bob 选择哪个整数,他都会获得 $$$0$$$ 分。