GCD Sum

You are given a multiset of $n$ integers, so the same value can appear several times. Split the multiset into $k$ nonempty groups, where every element belongs to exactly one group. For each group compute the greatest common divisor of its elements, then add those divisors together.

For every $k = 1, 2, \ldots, n$, find the largest sum you can obtain this way.

The first line contains the size of the multiset $n$ ($1 \leq n \leq 500\,000$).

The second line contains the $n$ positive integers of the sequence. Each integer is at most $10^{12}$.

Print $n$ lines. Line $i$ contains the largest sum of greatest common divisors over all splits of the multiset into $k = i$ groups.

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