Fenwick Tree Construction

Задан массив A из n натуральных чисел. Постройте дерево Фенвика, и выведите массив после каждой итерации добавления элемента к дереву.

Input

В первой строке находится размер массива n (1 ≤ n ≤ 100). В следующей строке находятся n натуральных чисел – элементы массива A (1 ≤ A[i] ≤ 10^9).

Output

Выведите n строк, в каждой из которых выведите n чисел – массив после очередной итерации добавления элемента к дереву Фенвика.

Examples