如果一个正整数序列 $(x_1, \dots, x_m)$ 满足 $x_1 = 1$，且对于每个 $1 < j \le m$，都有 $x_j = x_{j-1} + 1$ 或者 $x_j = x_k \cdot x_l$（其中 $0 < k \le l < j$），则称该序列是“好的”。例如，序列 $(1, 1)$ 和 $(1, 2)$ 都是好的，但序列 $(1, 3)$ 不是好的。对于给定的 $n$ 个整数 $w_1, \dots, w_n$，定义一个满足对于每个 $1 \le j \le m$ 都有 $1 \le x_j \le n$ 的整数序列 $(x_1, \dots, x_m)$ 的权值为： $$w_{x_1} + \dots + w_{x_m}$$ 例如，给定权重 $w_1 = 10, w_2 = 42, w_3 = 1$，序列 $(1, 1)$ 的权值为 $20$，序列 $(1, 3)$ 的权值为 $11$。对于 $1 \le v \le n$，定义 $s_v$ 为包含值 $v$ 的所有“好的”序列中，权值的最小值。
你的任务是确定 $s_1, \dots, s_n$ 的值。
输入格式
输入的第一行包含整数 $n$，即权重的数量。接下来的 $n$ 行包含整数权重 $w_1, \dots, w_n$。
输出格式
按顺序输出 $n$ 行，包含 $s_1, \dots, s_n$。
数据范围
对于所有测试数据，满足 $1 \le n \le 30\,000$ 且对于每个 $1 \le i \le n$，都有 $1 \le w_i \le 10^6$。
子任务
| 组别 | 分值 | 数据范围 |
|---|---|---|
| 1 | 11 | $n \le 10$ |
| 2 | 10 | $n \le 300, w_1 = \dots = w_n = 1$ |
| 3 | 10 | $n \le 300, w_1 = \dots = w_n$ |
| 4 | 9 | $n \le 1400, w_1 = \dots = w_n = 1$ |
| 5 | 45 | $n \le 5000$ |
| 6 | 15 | 无附加限制 |
样例
输入 1
3 10 42 1
输出 1
10 52 53