Фермер Джон выстроил \(N\) своих коров (\(2\le N\le 10^3\)), пронумерованных \(1\ldots N\),
для фотоснимка. Изначально ФД планировал, что \(i\)-ая корова слева будет корова
с номером \(a_i,\) и выписал перестановку \(a_1,a_2,\ldots,a_N\) на листке бумаги.
К несчастью этот листок украл фермер Нхож.
Однако, ФД сможет восстановить перестановку, которую он изначально
выписал. Перед тем, как листок с перестановкой был украден, Беси выписала
последовательность \(b_1,b_2,\ldots,b_{N-1}\) такую, что \(b_i=a_i+a_{i+1}\)
для всех \(1\le i<N.\)
Основываясь на информации от Беси, помогите ФД восстановить "лексикографически
минимальную" перестановку \(a\), которая может произвести \(b\). Перестановка \(x\)
лексикографически меньше перестановки \(y\), если для некоторого \(j\), \(x_i=y_i\)
для всех \(i<j\) и \(x_j<y_j\) (другими словами, две перестановки идентичны
до определённой точки, в которой \(x\) меньше чем \(y\)). Гарантируется, что
существует как минимум одна такая перестановка \(a\)
ОЦЕНИВАНИЕ:
- Тесты 2-4 удовлетворяют \(N\le 8.\)
- Тесты 5-10 не имеют дополнительных ограничений.
ФОРМАТ ВВОДА (файл photo.in):
Первая строка содержит одно целое число
\(N.\)
Вторая строка содержит \(N-1\) разделённых одиночными пробелами целых чисел
\(b_1,b_2,\ldots,b_{N-1}.\)
ФОРМАТ ВЫВОДА (файл photo.out):
Одна строка с \(N\) разделёнными одиночными пробелами целых чисел
\(a_1,a_2,\ldots,a_{N}.\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 6 7 6
|
3 1 5 2 4
|