Поликарп любит не только фотографировать, но и показывать свои фотографии друзьям. На своем личном сайте недавно он установил виджет, который может отображать n фотографий с возможностью их прокрутки. В каждый момент времени виджет показывает ровно одну фотографию с возможностью перехода к предыдущей/следующей. С первой фотографии можно перейти на вторую или n-ую, со второй — на третью или первую и т.д. Таким образом навигация осуществляется по циклу.

Коллекция Поликарпа состоит из m фотоальбомов, i-ый фотоальбом содержит a_i фотографий. Поликарп хочет, выбрать n фотографий и поместить их на новый виджет. Для того, чтобы посетителям сайта было интересно просматривать фото, он собирается разместить фотографии так, что никакие две фото с одного альбома не будут соседствовать (у каждой фотографии будет ровно два соседа, у первой — вторая и n-ая).

Помогите Поликарпу составить фотогалерею. Выберите n фотографий из его коллекции и разместите их в таком порядке, что никакие два фото из одного альбома не идут подряд.