Поликарп любит не только фотографировать, но и показывать свои фотографии друзьям. На своем личном сайте недавно он установил виджет, который может отображать n фотографий с возможностью их прокрутки. В каждый момент времени виджет показывает ровно одну фотографию с возможностью перехода к предыдущей/следующей. С первой фотографии можно перейти на вторую или n-ую, со второй — на третью или первую и т.д. Таким образом навигация осуществляется по циклу.
Коллекция Поликарпа состоит из m фотоальбомов, i-ый фотоальбом содержит ai фотографий. Поликарп хочет, выбрать n фотографий и поместить их на новый виджет. Для того, чтобы посетителям сайта было интересно просматривать фото, он собирается разместить фотографии так, что никакие две фото с одного альбома не будут соседствовать (у каждой фотографии будет ровно два соседа, у первой — вторая и n-ая).
Помогите Поликарпу составить фотогалерею. Выберите n фотографий из его коллекции и разместите их в таком порядке, что никакие два фото из одного альбома не идут подряд.
Выходные данные
Выведите единственное число -1, если решения не существует. В противном случае выведите n чисел t1, t2, ..., tn, где ti обозначает номер альбома i-ой фотографии на виджете. Альбомы нумеруются от 1 в порядке их задания во входных данных. Если решений несколько, то выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 3 5
|
3 1 3 2
|
|
2
|
10 2
5 5
|
2 1 2 1 2 1 2 1 2 1
|
|
3
|
10 3
1 10 3
|
-1
|