题目背景

Han24666 正在玩打怪游戏

题目描述

此时 Han24666 面前有 $n$ 个怪物, 第 $i$ 个怪血量为 $a_i$, 此时 Han24666 可以发动以下 $4$ 个操作:

1. 普通攻击, 对区间 $l-r$ 中每个怪物造成 $x$ 滴伤害，注意：只要区间内存在任意一个怪物的血量低于 $x$, 那么, Han24666只能造成该区间和最小怪物血量相等的伤害。
2. 技能：伤害，将区间 $l-r$ 中所有怪物的血量除以 $x$ ($x \ge 10$)向下取整
3. 大招： 压制，将区间 $l-r$ 中所有怪物的血量对 $x$ 取模
4. 请求军师：询问军师区间 $l-r$ 中所有怪物血量的和

而现在，你就是Han24666的军师，Han24666的所有操作你都知道，你需要回答每次操作 $4$

输入格式

第一行两个整数 $n$,$q$ 表示怪物的数量，操作的次数 第二行 $n$ 个整数 $a_i$，代表怪物的初始血量 接下来 $q$ 行，每行多个整数代表操作，有以下 $3$ 种格式

1. 1 l r x表示使用普攻，对 $l-r$ 所有怪物造成 $x$ 滴伤害，只要区间内存在任意一个怪物的血量低于$x$, 那么只能造成该区间和最小怪物血量相等的伤害。
2. 2 l r x使用技能，使 $l-r$ 所有怪物血量除以 $x$向下取整
3. 3 l r x使用大招，使 $l-r$ 所有怪物血量对 $x$ 取模
4. 4 l r请求军师，你需要回答 $l-r$ 所有怪物的血量总和

输出格式

输出多行每行一个整数表示每次 $4$ 询问的答案

输入样例

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

输出样例

14
9

样例解释

初始血量 3 4 5 6 7

第 $1$ 次操作 $2-4$ 区间血量 $-2$,区间最小血量为 $4$ ($>2$) 血量变为 3 2 3 4 7

第 $2$ 次操作 $1-3$ 区间血量 $\div 2$, 血量变为 1 1 1 4 7

第 $3$ 次操作 查询 $1-5$ 血量和，$1+1+1+4+7=14$

第 $4$ 次操作 $4-5$ 区间血量 $mod 5$, 变为1 1 1 4 2

第 $5$ 次操作 查询 $1-5$ 血量和，$1+1+1+4+2=9$

数据规模与规定

1. $1 \le n,q \le 10^5$
2. 存在$l \ge r$
3. 所有输入均不超过 $10^5$ 并且都为非负数
4. 对于每个 $2$ 操作，保证 $x \ge 10$

部分分详细见表