费解的gcd
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 \(n\) 的一个整数序列 \(A=a_1,a_2,...,a_n\)，有 \(q\) 次操作

  • 给定一个整数 \(p \in [1,n]\) 表示操作1，将 \(a_p\) 赋值为 \(0\)
  • 给定一个整数 \(0\) 表示操作2，查询序列 \(A\) 所有数的 \(\gcd\)，即最大公约数

为了减少IO规模，你只需要输出所有查询答案的和模上 \(998244353\) 后的值

注：\(\forall x \ge 0,\gcd(x,0)=x\)，你可以形象地将操作1理解为在 \(A\) 中删去了一个数

输入描述:

第一行两个整数分别表示 n\ (1 \le n \le 5 \times 10^5) 和 q\ (1 \le q \le 2n)
接下来一行 n 个整数 a_1,a_2,...,a_n(1 \le a_i \le 10^9)，表示序列 A
接下来一行 q 个整数，表示操作序列，格式可以参考题面和样例

保证至少存在一个操作2
保证所有的 p 互不相同

输出描述:

一行一个整数，表示答案，即 \sum ans_i \text{ mod } 998244353，ans_i 表示第 i 个操作2的答案
示例1

输入

复制 
5 6
2 4 8 12 24
0 1 2 0 5 0

输出

复制 
10

说明

总共三次操作2，分别为：
a=[2,4,8,12,24],ans=2
a=[0,0,8,12,24],ans=4
a=[0,0,8,12,0],ans=4
因此答案为 2+4+4=10
示例2

输入

复制 
2 1
1000000000 1000000000
0

输出

复制 
1755647

说明

记得对答案取模