题目描述

"第一分钟，Y 说，要有数列，于是便给定了一个正整数数列。

第二分钟，T 说，要能修改，于是便有了对一段数中每个数都除以一个数（下取整）的操作。

第三分钟，H 说，要能查询，于是便有了求一段数的和的操作。

第四分钟，D 说，要是 czoj 周赛 E 难度，于是便有了数据范围。

第五分钟，X 说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，Y 说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $64$ 位无符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。

所以这个神圣的任务就交给你了。

输入格式

第一行两个正整数 $n,m$，代表数列中数的个数和操作次数。

第二行 $n$ 个正整数，表示初始状态下数列中的数。

接下来 $m$ 行每行 $3 \sim 4$ 个整数 k l r (d)。

• $k=1$ 表示给 $[l,r]$ 中的每个数都除以一个数 $d$（下取整）。

• $k=2$ 表示询问 $[l,r]$ 中各个数的和。

输出格式

对于询问操作，每行输出一个回答。

输入输出样例 #1

输入 #1

5 2
1 3 5 7 9
1 2 5 2
2 1 5

输出 #1

11

说明/提示

【样例解释 #1】

操作后的序列为 $\{1,1,2,3,4\}$，总和为 $11$。

【样例 #2】

见下发文件。

该样例满足测试点 $1 \sim 4$ 的限制。

【样例 #3】

见下发文件。

该样例满足测试点 $13 \sim 14$ 的限制。

【样例 #4】

见下发文件。

该样例满足测试点 $19 \sim 22$ 的限制。

【数据范围】

对于所有数据，$1 \le n,m \le 5 \times 10^5$，$0 \le a_i \le 10^{14}$，$1 \le d \le 10^{14}$，$1 \le k \le 2$。

测试点编号	$n \le$	$m \le$	特殊性质	分值
$1 \sim 4$	$10^4$		无	$4$
$5 \sim 6$	$2 \times 10^4$
$7 \sim 8$	$3 \times 10^4$
$9 \sim 10$	$5 \times 10^4$
$11 \sim 12$	$10^5$		$A$
$13 \sim 14$			$B$
$15 \sim 16$			无
$17 \sim 18$	$2 \times 10^5$
$19 \sim 22$	$5 \times 10^5$			$7$

其中：

• 特殊性质 A：保证 $k=2$；

• 特殊性质 B：保证数据在范围内均匀随机生成。

大样例