Задачі
Дерево Фенвіка
Дерево Фенвіка
Дерево Фенвіка - це структура даних, яка дозволяє ефективно обчислювати \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