Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Переключатели света
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть квартира, состоящая из $$$n$$$ комнат, каждая из которых имеет свет, изначально выключенный.

Чтобы управлять светом в этих комнатах, владелец квартиры решил установить чипы в комнатах так, чтобы в каждой комнате был один чип, и каждый чип устанавливался в разное время. Более конкретно, времена установки представлены массивом $$$a_1, a_2, \ldots, a_n$$$, где $$$a_i$$$ — это момент времени (в минутах), в который чип устанавливается в $$$i$$$-ю комнату.

Как только чип установлен, он меняет статус света в комнате каждые $$$k$$$ минут — включает свет на $$$k$$$ минут, затем выключает его на следующие $$$k$$$ минут, затем снова включает на следующие $$$k$$$ минут и так далее. Другими словами, статус света меняется чипом в минуты $$$a_i$$$, $$$a_i + k$$$, $$$a_i + 2k$$$, $$$a_i + 3k$$$, $$$\ldots$$$ для $$$i$$$-й комнаты.

Какой самый ранний момент, когда все комнаты в квартире будут с включенным светом?

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — количество комнат в квартире и период чипов.

Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — моменты, когда устанавливаются чипы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — ответ на задачу. Если нет такого момента времени, в который свет горит во всех комнатах, выведите $$$-1$$$ вместо этого.

Пример
Входные данные
9
4 4
2 3 4 5
4 3
2 3 4 5
4 3
3 4 8 9
3 3
6 2 1
1 1
1
7 5
14 34 6 25 46 7 17
6 5
40 80 99 60 90 50
6 5
64 40 50 68 70 10
2 1
1 1000000000
Выходные данные
5
-1
10
8
1
47
100
-1
-1
Примечание

В первом наборе входных данных все переключатели будут включены в минуту $$$5$$$, ни один из них не успеет выключиться к этой минуте. Ответ — $$$5$$$.

Во втором наборе входных данных, поскольку $$$k=3$$$, свет в $$$1$$$-й комнате будет включен в минуты $$$2, 3, 4, 8, 9, 10, 14, \ldots$$$; в то время как свет в $$$4$$$-й комнате будет включен в минуты $$$5, 6, 7, 11, 12, 13, 17, \ldots$$$. Эти две последовательности не имеют общих чисел, поэтому свет в этих комнатах никогда не будет включен одновременно.

В третьем наборе входных данных можно заметить, что свет в $$$1$$$-й и $$$2$$$-й комнатах будет выключен в минуты $$$6$$$ и $$$7$$$, но чипы снова включат его в минуты $$$9$$$ и $$$10$$$. Свет в $$$3$$$-й и $$$4$$$-й комнатах также будет включен в минуту $$$10$$$, поэтому ответ — $$$10$$$.