There are **N** boxes. The i^{th} box contains a_{i} candies. The frog Om Nom is sitting in box number 1. Om Nom wants to collect as many candies as he can. However, Om Nom jumps in a peculiar fashion. Om Nom can jump from box number **j** to box number **i** only if *j divides i*. Whenever Om Nom lands in a box, he collects all the candies in that box. You have to report the maximum number of Candies that Om Nom can collect for all i from 1 to N if i is the last box that Om Nom visits.See the samples for more details.

**Constraints**

0<=a_{i}<=100000

1<=N<=100000

**Input**

The first line contains the number N.

The second line contains the array a , the i^{th} integer denoting the number of candies in the i^{th} box.

**Output**

Print N integers-the i^{th} integer should be the maximum number of candies that Om Nom can collect if the i^{th} box is his final box (i.e his sequence of jumps ends at i).