您有一个数组 $$$a$$$,由 $$$n$$$ 不同的正整数组成,编号从 $$$1$$$ 到 $$$n$$$。将 $$$p_k$$$ 定义为 $$$$$$p_k = \sum_{1 \le i, j \le k} a_i \bmod a_j,$$$$$$ 其中 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 所得的余数。您必须找到并打印 $$$p_1, p_2, \ldots, p_n$$$。
输入
第一行包含 $$$n$$$ — 数组的长度 ($$$2 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 空格分隔的不同整数 $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$, $$$a_i \neq a_j$$$ if $$$i \neq j$$$)。
输出
打印 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$。
示例
输入 #1
4 6 2 7 3
输出 #1
0 2 12 22
输入 #2
3 3 2 1
输出 #2
0 3 5