给定一个包含 $n$ 个整数的多重集（即允许重复元素的集合）。我们将该集合划分为 $k$ 个不相交的组，计算每一组元素的公约数（GCD），并将所有组的 GCD 之和相加。 对于每一个 $k = 1, 2, \dots, n$，求出通过这种方式能得到的最大和。
输入格式
输入的第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示集合的大小。 第二行包含 $n$ 个正整数，不超过 $10^{12}$，即给定的序列。
输出格式
输出 $n$ 行，每行包含一个整数，分别表示划分为 $1, 2, \dots, n$ 个子集时能得到的最大 GCD 之和。
子任务
| 子任务 | 数据范围 | 分值 |
|---|---|---|
| 1 | $n \le 7$ | 5 |
| 2 | $n \le 15$ | 5 |
| 3 | $n \le 100, a_i \le 500$ | 8 |
| 4 | $n \le 2000, a_i \le 2000, a_i$ 互不相同 | 8 |
| 5 | $n \le 2000$ | 14 |
| 6 | $a_i$ 互不相同 | 25 |
| 7 | 无附加限制 | 35 |
样例
输入 1
4 10 9 10 3
输出 1
1 13 23 32
说明 1
当 $k = 2$ 时，最优划分为 $(10, 10)$ 和 $(9, 3)$，得到的和为 $10 + 3 = 13$。当 $k = 3$ 时，最优划分为 $(10), (10)$ 和 $(9, 3)$，得到的和为 $23$。
输入 2
8 15 25 29 30 43 44 45 55
输出 2
1 56 101 145 188 221 256 286