e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Дерево Фенвика

Дерево Фенвика

Дерево Фенвика - это структура данных, которая позволяет эффективно вычислять префиксные суммы.

Для числа t обозначим через h(t) наибольшее k, для которого t делится на 2k. Например, h(24) = 3, h(5) = 0. Пусть l(t) = 2h(t), например l(24) = 8, l(5) = 1.

Рассмотрим массив a[1], a[2], ..., a[n] целых чисел. Деревом Фенвика для этого массива является массив b[1], b[2], ..., b[n] такой что

prb6233.

Таким образом

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 (1n100000). Вторая строка содержит n целых чисел - элементы массива. Значения элементов по модулю не превосходят 109.

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

Вывести n чисел - элементы массива a'. Если существует несколько решений, то вывести любое.

Лимит времени 3 секунды
Лимит использования памяти 256 MiB
Входные данные #1
6
3 -1 4 1 -5 9
Выходные данные #1
0
-1
1
1
0
9
Источник Northern Subregional Programming Contest 2008
Enchanted Mirror
Ground Works