B. Игра с перестановкой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

n детей стоят по кругу и играют в игру. Дети пронумерованы по часовой стрелке таким образом, что номера образуют перестановку a1, a2, ..., an длины n. Это последовательность целых чисел, такая, что каждое число от 1 до n встречается в ней ровно один раз.

Игра состоит из m шагов. На каждом шаге текущий ведущий на позиции i отсчитывает ai человек по часовой стрелке, начиная со следующего человека. Тот, на кого ведущий указал последним, становится новым ведущим.

Вам дана последовательность l1, l2, ..., lm — номера ведущих в начале каждого шага. Ребенок с номером l1 — первый ведущий.

Напишите программу, которая восстановит возможную перестановку a1, a2, ..., an. Если существует несколько решений, то выведите любое. Если нет решения, то выведите -1.

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

В первой строке записаны два целых числа n, m (1 ≤ n, m ≤ 100).

Во второй строке записаны m целых чисел l1, l2, ..., lm (1 ≤ li ≤ n) — номера ведущих в начале каждого шага.

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

Выведите такую перестановку длины n a1, a2, ..., an, что номера ведущих при игре с ней будут в точности l1, l2, ..., lm. Если существует несколько решений, то выведите любое.

Если не существует перестановки, удовлетворяющей описанным условиям, выведите -1.

Примеры
Входные данные
4 5
2 3 1 4 4
Выходные данные
3 1 2 4
Входные данные
3 3
3 1 2
Выходные данные
-1
Примечание

Рассмотрим порядок ведущих в первом примере:

  • Ребенок 2 начинает.
  • После 2 ведущим становится 2 + a2 = 3.
  • После 3 ведущим становится 3 + a3 = 5. Так как это больше, чем 4, по кругу переходит к 1.
  • После 1 ведущим становится 1 + a1 = 4.
  • После 4 ведущим становится 4 + a4 = 8. Значит по кругу это остается 4.