Задачи
Дерево Фенвика
Дерево Фенвика
Дерево Фенвика - это структура данных, которая позволяет эффективно вычислять \textit{префиксные суммы}.
Для числа \textbf{t} обозначим через \textbf{h(t)} наибольшее k, для которого \textbf{t} делится на \textbf{2^k}. Например, \textbf{h(24) = 3}, \textbf{h(5) = 0}. Пусть \textbf{l(t) = 2^\{h(t)\}}, например \textbf{l(24) = 8}, \textbf{l(5) = 1}.
Рассмотрим массив \textbf{a\[1\]}, \textbf{a\[2\]}, ..., \textbf{a\[n\] }целых чисел. Деревом Фенвика для этого массива является массив \textbf{b}\[\textbf{1}\], \textbf{b}\[\textbf{2}\], ..., \textbf{b}\[\textbf{n}\] такой что
\includegraphics{https://static.e-olymp.com/content/c6/c6e933b903f7e83fe83dc85496e07e2f5d4d9d03.jpg}
.
Таким образом
\textbf{b\[1\] = a\[1\]},
\textbf{b\[2\] = a\[1\] + a\[2\]},
\textbf{b\[3\] = a\[3\]},
\textbf{b\[4\] = a\[1\] + a\[2\] + a\[3\] + a\[4\]},
\textbf{b\[5\] = a\[5\]},
\textbf{b\[6\] = a\[5\] + a\[6\]},
...
Например, деревом Фенвика для массива
\textbf{a = (3, -1, 4, 1,-5, 9)}
является массив
\textbf{b = (3, 2, 4, 7,-5, 4)}.
Будем называть массив \textit{само-Фенвиком}, если он совпадает с деревом Фенвика. Например, массив выше не является само-Фенвиком, а массив \textbf{a = (0,-1, 1, 1, 0, 9)} таковым является.
Задан массив \textbf{a}. Разрешается изменить значения некоторых элементов не меняя их порядок чтобы получить новый массив \textbf{a'} который будет само-Фенвиком. Решите поставленную задачу, изменив наименьшее количество элементов.
\InputFile
Первая строка содержит количество элементов в массиве \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}). Вторая строка содержит \textbf{n} целых чисел - элементы массива. Значения элементов по модулю не превосходят \textbf{10^9}.
\OutputFile
Вывести \textbf{n} чисел - элементы массива \textbf{a'}. Если существует несколько решений, то вывести любое.
Входные данные #1
6 3 -1 4 1 -5 9
Выходные данные #1
0 -1 1 1 0 9