A multi-set (i.e. a set with possible repetitions) of $n$ integers is given. We split the set into $k$ disjoint groups, for every group we compute the greatest common divisor of its elements, and sum all the subsets' GCDs.</p>

For every $k = 1, 2, \ldots, n$, determine the maximal sum which can be obtained this way

입력 형식

In the first line of input there is a single integer $n$ ($1 \leq n \leq 500\,000$) -- the cardinality of the set. In the second line, there are $n$ positive integers, not exceeding $10^{12}$ -- the given sequence.

출력 형식

Output $n$ line scontaining one integer each -- the best sum of GCDs when partitioning into $1$, $2$, $\ldots$, $n$ subsets.

예제 입력 1

4
10 9 10 3

예제 출력 1

1
13
23
32

예제 입력 2

8
15 25 29 30 43 44 45 55

예제 출력 2

1
56
101
145
188
221
256
286

힌트

For $k = 2$, the best partition is $(10,10)$ and $(9,3)$, giving the sum of $10+3 = 13$. For $k=3$, the best partition is $(10)$, $(10)$ and $(9,3)$ with the sum of $23$.