В магазине продается \(n\) предметов. Цена \(i\)-го предмета равна \(a_i\). Владелец магазина хочет приравнять цены всех предметов. Но он хочет изменить цены аккуратно.
Фактически, владелец магазина может изменять цену какого-то предмета \(i\) таким образом, что разница между старой ценой этого предмета \(a_i\) и новой ценой \(b_i\) не превышает \(k\). Другими словами, должно выполняться условие \(|a_i - b_i| \le k\) (\(|x|\) — это абсолютное значение \(x\)).
Он может изменять цену каждого предмета не более одного раза. Заметьте, что он может оставить старые цены некоторым предметам. Новая цена \(b_i\) каждого предмета \(i\) должна быть положительной (то есть должно выполняться условие \(b_i > 0\) для всех \(i\) от \(1\) до \(n\)).
Ваша задача — найти максимально возможную равную цену \(B\) всех предметов с ограничением, что для всех предметов должно выполняться условие \(|a_i - B| \le k\) (где \(a_i\) равно старой цене предмета, а \(B\) — это одинаковая новая цена всех предметов) или сказать, что невозможно найти такую цену \(B\).
Заметьте, что выбранная цена \(B\) должна быть целой.
Вам необходимо ответить на \(q\) независимых запросов.
Выходные данные
Выведите \(q\) целых чисел, где \(i\)-е целое число является ответом \(B\) на \(i\)-й запрос.
Если невозможно приравнять цены всех заданных предметов с ограничением, что для всех предметов должно выполняться условие \(|a_i - B| \le k\) (где \(a_i\) равно старой цене предмета, а \(B\) равно новой равной цене всех предметов), выведите -1. Иначе выведите максимально возможную равную цену всех предметов.
Примечание
В первом запросе тестового примера Вы можете выбрать цену \(B=2\). Легко заметить, что разница между каждой старой ценой и новой ценой \(B=2\) не превышает \(1\).
В первом запросе тестового примера Вы можете выбрать цену \(B=6\), тогда все разницы между старыми ценами и новыми ценами \(B=6\) не превысит \(2\).
В третьем запросе тестового примера Вы не можете выбрать никакую подходящую цену \(B\). Для любого значения \(B\) хотя бы одно условие из двух будет нарушено: \(|1-B| \le 2\), \(|6-B| \le 2\).
В четвертом запросе тестового примера все значения \(B\) между \(1\) и \(7\) являются корректными. Но самое максимальное равно \(7\), поэтому оно является ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|