최대공약수 합

정수 $n$개로 이루어진 다중집합이 주어진다. 같은 수가 여러 번 나올 수 있다. 이 다중집합을 비어 있지 않은 $k$개의 그룹으로 나누면 모든 원소는 정확히 한 그룹에 속한다. 그룹마다 원소의 최대공약수를 구한 다음, 구한 값을 모두 더한다.

$k = 1, 2, \ldots, n$ 각각에 대해 이렇게 얻을 수 있는 합의 최댓값을 구하라.

첫째 줄에 다중집합의 크기 $n$이 주어진다 ($1 \leq n \leq 500\,000$).

둘째 줄에 수열을 이루는 양의 정수 $n$개가 주어진다. 각 정수는 $10^{12}$ 이하이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 다중집합을 $k = i$개의 그룹으로 나눌 때 최대공약수의 합이 가질 수 있는 최댓값을 출력한다.

수열이 $10, 9, 10, 3$이면 $k = 2$의 최적 분할은 $(10, 10)$과 $(9, 3)$이고 합은 $10 + 3 = 13$이다. $k = 3$의 최적 분할은 $(10)$, $(10)$, $(9, 3)$이고 합은 $23$이다.