#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define inf 1e9
#define pii pair <int, int>
const int mod = 1e9 + 7;
inline int read () {
	int x = 0, f = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar ();
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ();
	return x * f;
}
inline void write (int x) {
	if (x < 0) x = -x, putchar ('-');
	if (x >= 10) write (x / 10);
	putchar (x % 10 + '0');
}
inline int quickmod (int x, int y) {
	int Ans = 1;
	while (y) {
		if (y & 1) Ans = (1ll * Ans * x) % mod;
		x = (1ll * x * x) % mod;
		y >>= 1;
	}
	return Ans;
}
int n;
int a[500005];
int m;
int ans;
int s[500005];
pii b[500005];
map <int, int> M;

priority_queue <int, vector <int>, greater <int> > Q;
int chk() {
	if(!m || Q.empty()) return 0;
	int p2 = s[m-1] + b[m].first;
	int p3 = __gcd(s[m-2], b[m].first) + b[m-1].first;
	int mx = max(p2, p3);
	int tp = Q.top();
	if(mx < tp) return 0;
	ans -= tp, Q.pop(), M[tp]++;
	if(mx == p2) {
		ans += b[m].first;
		if(b[m].second != 1) M[b[m].first] += b[m].second - 1;
		m--;
	}
	else {
		swap(b[m], b[m-1]);
		s[m-1] = __gcd(s[m-2], b[m-1].first), s[m] = __gcd(s[m-1], b[m].first);
		ans += b[m].first;
		if(b[m].second != 1) M[b[m].first] += b[m].second - 1;
		m--;
	}
	return 1;
}
signed main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; i++) {
		if(i == 1 || a[i] != a[i-1]) b[++m] = mp(a[i], 1);
		else b[m].second++;
	}
	for(int i = 1; i <= m; i++) s[i] = __gcd(s[i-1], b[i].first);//, printf("{%lld %lld}\n", b[i].first, b[i].second);
	if(m == 1) {
		for(int i = 1; i <= n; i++) write(a[1] * i), putchar('\n');
		return 0;
	}
	if(m == 2) {
		write(s[2]), putchar('\n');
		for(int i = 2; i <= b[2].second + 1; i++) write(b[1].first + (i - 1) * b[2].first), putchar('\n');
		for(int i = 2; i <= b[1].second; i++) write(b[1].first * i + b[2].first * b[2].second), putchar('\n');
		return 0;
	}
	write(s[m]), putchar('\n');
	ans = 0, n--;
	while(n--) {
		if(m == 1) {
			ans += b[1].first;
			if(b[m].second != 1) M[b[m].first] += b[m].second - 1;
			m--;
		}
		while(chk());
		if(!m) {
			auto it = *(--M.end());
			ans += it.first, it.second--;
			if(!it.second) M.erase(it.first);
			write(ans), putchar('\n');
		}
		else {
			int p1 = -inf;
			if(!M.empty()) p1 = (*(--M.end())).first + s[m];
			int p2 = s[m-1] + b[m].first;
			int p3 = __gcd(s[m-2], b[m].first) + b[m-1].first;
			int mx = max(max(p1, p2), p3);
			if(mx == p1) {
				auto it = *(--M.end());
				ans += it.first, it.second--, Q.push(it.first);
				if(!it.second) M.erase(it.first);
				write(ans + s[m]), putchar('\n');
			}
			else if(mx != p3) {
				ans += b[m].first;
				if(b[m].second != 1) M[b[m].first] += b[m].second - 1;//, printf("!!\n");
				m--;
//				printf("A:%lld\n", p1);
				write(ans + s[m]), putchar('\n');
			}
			else {
				swap(b[m], b[m-1]);
				s[m-1] = __gcd(s[m-2], b[m-1].first), s[m] = __gcd(s[m-1], b[m].first);
				ans += b[m].first;
				if(b[m].second != 1) M[b[m].first] += b[m].second - 1;
				m--;
				write(ans + s[m]), putchar('\n');
			}
		}
	}
	return 0;
}
/*
7
6 10 11 12 12 15 30
*/