AB5.

初始时我们有一个集合：

$$S=\{a_1,\dots,a_N\}$$

其中 $a_1,\dots,a_N$ 两两不同。你需要维护两类操作：

1. 向集合中加入 $x$（即 $S \gets S \cup \{x\}$），保证此时 $x \notin S$；
2. 从集合中删除 $x$（即 $S \gets S \setminus \{x\}$），保证此时 $x \in S$。

我们关心所有非空子集的最大公约数之和，记为：

$$f(S)=\sum_{Q\subseteq S,\ |Q|>0} \gcd(Q)$$

其中 $\gcd(Q)$ 表示集合 $Q$ 中所有元素的最大公约数。若 $S$ 为空集，则定义 $f(S)=0$。

你的任务是求：

• 初始集合的 $f(S)$；
• 以及每次操作之后的 $f(S)$。

由于答案可能非常大，只需输出它们对 $10^9+7$ 取模后的结果。

请编写程序 gcd2.cpp 完成上述任务。

输入格式

第一行两个整数 $N,Q$，分别表示初始集合中的元素个数与操作个数。
第二行包含 $N$ 个整数 $a_1,\dots,a_N$。
接下来 $Q$ 行，每行两个整数 $t,x$：

• 若 $t=1$，表示将 $x$ 加入集合；
• 若 $t=2$，表示将 $x$ 从集合中删除。

输出格式

输出 $Q+1$ 行：

• 第 1 行为初始集合的 $f(S)$；
• 之后每行分别为每次操作后的 $f(S)$。

数据范围

$$0 \le N,Q \le 2 \times 10^5$$ $$1 \le a_i,x \le 2 \times 10^6$$

子任务与评分

子任务	分值	$N \le$	$Q \le$	$a_i,x \le$
1	5	10		$2 \times 10^6$
2	12	$2 \times 10^5$	0
3	13	0	3000	3000
4	12		$2 \times 10^5$
5	28			$10^5$
6	30	$2 \times 10^5$		$2 \times 10^6$

样例

输入

3 3
2 4 8
2 2
1 16
1 39

输出

24
16
48
94

样例说明

• 当 $S=\{2,4,8\}$ 时：

$$f(S)=\gcd(\{2\})+\gcd(\{4\})+\gcd(\{8\})+\gcd(\{2,4\})+\gcd(\{2,8\})+\gcd(\{4,8\})+\gcd(\{2,4,8\})$$$$=2+4+8+2+2+4+2=24$$

• 当 $S=\{4,8\}$ 时：

$$f(S)=\gcd(\{4\})+\gcd(\{8\})+\gcd(\{4,8\})=4+8+4=16$$

• 当 $S=\{4,8,16\}$ 时：

$$f(S)=4+8+16+4+4+8+4=48$$

• 当 $S=\{4,8,16,39\}$ 时：

所有非空子集的 gcd 之和为：

$$4+8+16+39+4+4+1+8+1+1+4+1+1+1+1=94$$