Có n sản phẩm trong cửa hàng. Giá của sản phẩm thứ i là a[i]. Chủ cửa hàng muốn thay đổi giá của tất cả các sản phẩm thành b. Tuy nhiên, anh muốn thay đổi giá mới b phải là số nguyên, độ lệch giữa giá mới và giá cũ không quá k (nghĩa là |a[i] – b| ≤ k) và b ≥ 0.

Anh ta có thể thay đổi giá của mỗi sản phẩm không quá 1 lần và có thể giữ nguôn giá cũ của một số sản phẩm.

Nhiệm cụ của bạn là tìm ra mức giá mới b tối đa có thể của tất cả các sản phẩm với các yêu cầu như đã nêu trên.

Bạn phải trả lời q truy vấn độc lập

Đầu vào

Dòng đầu tiên của đầu vào chứa một số nguyên q là số lượng truy vấn. Mỗi truy vấn gồm hai dòng:

- Dòng đầu tiên chứa hai số nguyên n và k;

- Dòng thứ hai chứa n số nguyên a[1], a[2], …, a[n], trong đó a[i] là giá của sản phẩm thứ i.

Ràng buộc

1 ≤ q ≤ 100; 1 ≤ n ≤ 100, 1 ≤ k ≤ 10⁸; 1 ≤ a[i] ≤ 10⁸

Đầu ra:

In ra q dòng, trong đó số nguyên thứ i là câu trả lời của truy vấn thứ i. Cụ thể, nếu có thể thực hiện được yêu cầu đề bài thì in ra giá b lớn nhất có thể. Ngược lại, in ra số -1.