P3987 我永远喜欢珂朵莉~

题目描述

给珂朵莉一个长为 $n$ 的非负数序列 $a$，支持以下两个操作：

• $\verb!1 l r x!$：把区间 $[l,r]$ 中所有 $x$ 的倍数除以 $x$。
• $\verb!2 l r!$：查询区间 $[l,r]$ 内元素的和。

珂朵莉很可爱，所以你要帮珂朵莉写这个题。

输入格式

第一行两个数表示 $n,m$。

第二行 $n$ 个非负整数表示 $a_i$。

之后 $m$ 行每行一个操作：

• $\verb!1 l r x!$：把区间 $[l,r]$ 中所有 $x$ 的倍数除以 $x$。
• $\verb!2 l r!$：查询区间 $[l,r]$ 内元素的和。

输出格式

对于每次询问，输出一行一个数表示答案。

输入输出样例 #1

输入 #1

5 3
1 2 3 4 5
2 1 5
1 1 5 2
2 1 5

输出 #1

15
12

说明/提示

数据范围及约定

$1 \le n , m \le 10^5$，$0 \le a_i \le 5\times 10^5$，$1 \le x \le 5\times 10^5$。