Building a Fenwick Tree

You are given an array A consisting of n natural numbers. Your task is to construct a Fenwick tree and display the array after each element is added to the tree.

Input

The first line contains an integer n (1 ≤ n ≤ 100), which represents the size of the array. The second line contains n natural numbers, which are the elements of the array A (1 ≤ A[i] ≤ 10^9).

Output

Produce n lines of output, where each line contains n numbers. Each line should represent the state of the array after adding the corresponding element to the Fenwick tree.

Examples