Дерево Фенвика
Дерево Фенвика - это структура данных, которая позволяет эффективно вычислять префиксные суммы.
Для числа 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'. Если существует несколько решений, то вывести любое.