该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Iris想利用自己的高等数学知识赚点钱，所以在学习了创新创业基础之后，她准备开一家“平价店“。

Iris一共购进了 n 件商品，第 i 件商品的成本价是 ai 元。对于每一件商品，Iris至多可以将成本价上下浮动 k 元作为实际售价 bi 元，即对于每件商品有 | ai - bi | ≤ k 。Iris似乎对“平价”有所误解，因为她准备把所有的售价调整为相同的价格。

Iris想发财，所以调整后的所有价格（也可以不调整部分价格）必须是正整数。她想问你是否能够将所有的售价设定为同一价格 B ，即对于所有商品有 | ai - B | ≤ k ，如果可以的话，B 最大是多少？

题目有 q 组独立询问。

Input

第一行包括一个正整数 q ( 1 ≤ q ≤ 100 ) ，表示询问的总数。

每组询问包括两行：

第一行包括两个整数 n 和 k ( 1 ≤ n ≤ 100, 1 ≤ k ≤ 10^8 )，分别表示商品数和价格可浮动量。

第二行包括 n 个整数 a​1​, a​2, …, a​n​，分别表示第 i 件商品的成本价。1<=ai<=1e8

Output

输出共 q 行，第 i 行为第 i 组询问的答案。

如果存在满足题意得 ​B​，则在对应行输出，否则输出 -1。

Samples

4
5 1
1 1 2 3 1
4 2
6 4 8 5
2 2
1 6
3 5
5 2 5

2
6
-1
7