题目描述

定义一个整数序列 $B=(B_1,B_2,\dots,B_k)$ 的分数为

$$\sum_{i=1}^{k} \sum_{j=1}^{i-1} \gcd (B_i,B_j) \times 2^{(i-j-1)}$$

给出一个整数序列 $A=(A_1,A_2,\dots,A_N)$，求出以下问题在 $m=1,2,\dots,N$ 时的答案：

• 序列 $A=(A_1,A_2,\dots,A_m)$ 的分数，对 $998244353$ 取模后的值。

输入格式

第一行包含两个整数 $n, q$（$1\le N\le 5 \times 10^5$），表示数组的长度和询问的个数。

第二行包含 $n$ 个整数，表示数组 $A$（$1\le A_i\le 10^5$）。

输出格式

输出 $N$ 行，第 $i$ 行表示当 $m=i$ 时的答案。

3
9 6 4

0 3 7

5
3 8 12 6 9

0 1 11 33 70 

10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127

0 2 16 23 62 543 823 950 1661 3864