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

Вхідні дані

У першому рядку знаходиться розмір масиву n (1 ≤ n ≤ 100). В наступному рядку знаходяться n натуральних чисел – елементи масиву A (1 ≤ Ai ≤ 109).

Вихідні дані

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