Есть квартира, состоящая из \(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\)-й комнаты.
Какой самый ранний момент, когда все комнаты в квартире будут с включенным светом?
Выходные данные
Для каждого набора входных данных выведите одно целое число — ответ на задачу. Если нет такого момента времени, в который свет горит во всех комнатах, выведите \(-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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|