E. Djangle 的数据结构
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Djangle 很喜欢研究数组操作！

这次，他拿到了一个长度为 $$$n$$$ 的正整数序列 $$$a$$$，并希望对它进行一些操作和查询。他对 gcd（最大公约数） 的性质十分感兴趣，并提出了如下两种操作，每种操作均包含三个参数 $$$l,r,x$$$：

  • 操作0：区间赋值操作：将区间 $$$[l, r]$$$ 内的所有元素修改为某个给定的正整数 $$$x$$$，即： $$$$$$ a_i := x, \quad \forall i \in [l, r] $$$$$$
  • 操作1：GCD 查询与更新操作：
    • 首先，计算区间 $$$[l, r]$$$ 内所有元素与某个给定的正整数 $$$x$$$ 的 gcd 之和，即： $$$$$$ \sum_{i=l}^{r} \gcd(a_i, x) $$$$$$
    • 然后，将区间 $$$[l, r]$$$ 内的所有元素更新为 $$$\gcd(a_i, x)$$$，即： $$$$$$ a_i := \gcd(a_i, x), \quad \forall i \in [l, r] $$$$$$

Djangle 太懒了，他甚至懒得算答案。所以他请你帮助他实现一个程序。

Input

第一行输入一个整数 $$$T$$$（$$$1 \le T \le 10^5$$$），表示数据组数。

接下来对每组数据输入如下：

  • 第一行包含两个整数 $$$n$$$ 和 $$$q$$$（$$$1 \le n, q \le 10^5$$$, $$$\sum n, \sum q \le 10^5$$$），分别表示数组的长度和操作的次数。
  • 第二行包含 $$$n$$$ 个正整数 $$$a_1, a_2, \dots, a_n$$$（$$$1 \le a_i \le 2^{30}$$$），表示初始数组。
  • 接下来的 $$$q$$$ 行，每行描述一个操作：
    • 如果是操作 0，格式为 0 l r x，表示将区间 $$$[l, r]$$$ 内的所有元素修改为 $$$x$$$（$$$1 \le x \le 2^{30}$$$）。
    • 如果是操作 1，格式为 1 l r x，表示执行 GCD 查询与更新操作（$$$1 \le x \le 2^{30}$$$）。
Output

对于每个操作 1，输出计算得到的 gcd 之和。

Example
Input
2
5 5
32 16 6 34 47
1 3 4 93
0 2 4 46
0 1 2 81
1 3 5 2
1 3 3 69
10 10
974 560 4 870 975 322 233 742 917 611
1 2 6 766
0 2 6 562
1 4 10 920
1 6 10 353
0 7 10 481
0 9 9 207
1 1 3 43
1 1 10 524
1 1 2 710
0 7 10 190
Output
4
5
1
9
11
5
3
12
2
Note

对于第一组数据：

操作$$$a_1$$$$$$a_2$$$$$$a_3$$$$$$a_4$$$$$$a_5$$$输出
初始$$$32$$$$$$16$$$$$$6$$$$$$34$$$$$$47$$$
1 3 4 93$$$32$$$$$$16$$$$$$3$$$$$$1$$$$$$47$$$$$$4$$$
0 2 4 46$$$32$$$$$$46$$$$$$46$$$$$$46$$$$$$47$$$
0 1 2 81$$$81$$$$$$81$$$$$$46$$$$$$46$$$$$$47$$$
1 3 5 2$$$81$$$$$$81$$$$$$2$$$$$$2$$$$$$1$$$$$$5$$$
1 3 3 69$$$81$$$$$$81$$$$$$1$$$$$$2$$$$$$1$$$$$$1$$$