15206번 - GCD-sum 다국어

문제

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.

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.

제한

힌트

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ドル$.