Дерево Фенвіка#6233

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

3 секунди

256 мегабайтів

Дуже легка

Дерево Фенвіка — це структура даних, яка ефективно підтримує префіксні суми.

Для числа $t$ позначимо $h (t)$ як найбільше $k$ , таке що $t$ ділиться на $2^{k}$ 2^k. Наприклад, $h (24) = 3$ h(24) = 3, $h (5) = 0$ h(5) = 0. Нехай $l (t) = 2^{h (t)}$ l(t) = 2^{h(t)}; наприклад, $l (24) = 8$ l(24) = 8, $l (5) = 1$ l(5) = 1.

Розглянемо масив $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n цілих чисел. Деревом Фенвіка для цього масиву є масив $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n такий, що

Таким чином:

$b_{1} = a_{1}$ b_1 = a_1
$b_{2} = a_{1} + a_{2}$ b_2 = a_1 + a_2
$b_{3} = a_{3}$ b_3 = a_3
$b_{4} = a_{1} + a_{2} + a_{3} + a_{4}$ b_4 = a_1 + a_2 + a_3 + a_4
$b_{5} = a_{5}$ b_5 = a_5
$b_{6} = a_{5} + a_{6}$ b_6 = a_5 + a_6
$\dots$

Наприклад, деревом Фенвіка для масиву

$a = (3, - 1, 4, 1, - 5, 9)$ a = (3, -1, 4, 1, -5, 9)

є масив

$b = (3, 2, 4, 7, - 5, 4)$ b = (3, 2, 4, 7, -5, 4).

Називатимемо масив само-Фенвіком, якщо він збігається із своїм деревом Фенвіка. Наприклад, масив вище не є само-Фенвіком, а масив $a = (0, - 1, 1, 1, 0, 9)$ a = (0, -1, 1, 1, 0, 9) є таким.

Задано масив $a$ . Дозволяється змінити значення деяких елементів (не змінюючи їх порядок), щоб отримати новий масив $a^{'}$ a', який має бути само-Фенвіком. Знайдіть спосіб це зробити, змінивши якомога менше елементів.

Вхідні дані

Перший рядок містить $n$ ( $1 \leq n \leq 100000$ 1 \le n \le 100000) — кількість елементів у масиві. Другий рядок містить $n$ цілих чисел — елементи масиву. Значення елементів за модулем не перевищують $1 0^{9}$ 10^9.

Вихідні дані

Виведіть $n$ чисел — елементи масиву $a^{'}$ a'. Якщо існує кілька розв'язків, виведіть будь-який.

Приклади

Приклад 1

Loading

2^{k}

h (24) = 3

h (5) = 0

l (t) = 2^{h (t)}

l (24) = 8

l (5) = 1

a_{1}, a_{2}, \dots, a_{n}

b_{1}, b_{2}, \dots, 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^{'}

1 \leq n \leq 100000

1 0^{9}

a^{'}