暂无测试数据。

$\text{Mila}$ 在迷宫的门前发现了一个魔法序列 $a$，只有对这个序列进行一些操作，门才能打开。

$\text{Mila}$ 会两种可以修改这个序列的魔法和一种可以查询的魔法，共三种魔法。

已知魔法序列的长度为 $n$，$\text{Mila}$ 使用了 $q$ 次魔法，每次使用魔法相当于进行了一次操作，所以操作有三种：

1. 将序列的一个区间 $[l,r]$ 内每个数对 $c$ 取模。
2. 将序列的一个区间 $[l,r]$ 内每个数除以 $c$ 后，并向下取整。
3. 询问一个区间 $[l,r]$ 内所有数的和。

但是序列有点长，$\text{Mila}$ 使用魔法的次数也比较多，于是只好求助于你，帮忙回答第三种操作的结果。

输入格式

第一行输入两个以空格隔开的整数 $n,q$，含义如题所示。

第二行输入 $n$ 个以空格隔开的数字表示这个序列，第 $i$ 个数为 $a_i$。

下面 $q$ 行每行第一个数为 $id$：

1. 如果 $id=1$，那么再输入三个数 $l,r,c$，表示对 $[l,r]$ 区间进行 $1$ 操作。
2. 如果 $id=2$，那么再输入三个数 $l,r,c$，表示对 $[l,r]$ 区间进行 $2$ 操作。
3. 如果 $id=3$，那么再输入两个数 $l,r$，表示询问 $[l,r]$ 区间内的和。

输出格式

对于每个 $3$ 操作，输出一行，包含一个整数表示这个区间的和。

数据范围

对于 $20\%$ 的数据，有 $n,q\leq 10^3$。

对于另外 $20\%$ 的数据，保证没有 $1$ 操作。

对于另外 $20\%$ 的数据，保证没有 $2$ 操作。

对于 $100\%$ 的数据，有 $1\leq n,q\leq 10^5,1\leq a_i,c\leq 10^9$，其中 $a_i$ 表示魔法序列上第 $i$ 位初始的值。

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

5

3 4
2 6 3
3 1 1
1 1 2 7
2 3 3 1
3 2 3

2
9