题目背景

点我进入原题提交页面

题目描述

定义一个正整数序列 $B = (B_1, B_2, \dots, B_k)$ 的 得分 为 $\displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1})$。
给定一个正整数序列 $A = (A_1, A_2, \dots, A_N)$，对于 $m = 1, 2, \dots, N$，解决以下问题。

• 序列 $(A_1, A_2, \dots, A_m)$ 有 $2^m - 1$ 个非空子序列。计算所有这些子序列的得分之和，结果对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$。

第二行输入 $A_1,A_2,\cdots,A_N$

输出格式

输出一共输出 $N$ 行。

3
9 6 4

0
3
11

5
3 8 12 6 9

0
1
13
57
155

10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127

0
2
14
35
97
372
866
1859
4273
43287

数据规模与约定

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^5$