You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

"第一分钟，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$。

其中：

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

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

大样例