Дерево Фенвіка
Дерево Фенвіка - це структура даних, яка дозволяє ефективно обчислювати префіксні суми.
Для числа t побозначимо через h(t) найбільше k, для якого t ділиться на 2^k. Наприклад, h(24) = 3, h(5) = 0. Нехай l(t) = 2^{h(t)}, наприклад l(24) = 8, l(5) = 1.
Розглянемо масив a[1], a[2], ..., a[n] цілих чисел. Деревом Фенвіка для цього масиву є масив b[1],b[2], ..., b[n] такий що
.
Таким чином
b[1] = a[1],
b[2] = a[1] + a[2],
b[3] = a[3],
b[4] = a[1] + a[2] + a[3] + a[4],
b[5] = a[5],
b[6] = a[5] + a[6],
...
Наприклад, деревом Фенвіка для масива
a = (3, -1, 4, 1,-5, 9)
є масив
b = (3, 2, 4, 7,-5, 4).
Будемо називати масив само-Фенвіком, якщо він співпадає з деревом Фенвіка. Наприклад, масив вище не є само-Фенвіком, а масив a = (0,-1, 1, 1, 0, 9) є таким.
Задано масив a. Дозволяється змінити значення деяких елементів не змінюючи їх порядок щоб отримати новий масив a', який буде само-Фенвіком. Розв'яжіть поставлену задачу, змінивши найменьшу кількість елементів.
Вхідні дані
Перший рядок містить кількість елементів у масиві n (1 ≤ n ≤ 100000). Другий рядок містить n цілих чисел - елементи масиву. Значення елементів по модулю не перевищують 10^9.
Вихідні дані
Вивести n чисел - елементы масиву a'. Якщо існує декілька розв'язків, то виведіть довільний.