题目描述

给定 $N$，$Q$ 和 $A=(a_1,\\ldots,a_N)$。
处理以下 $Q$ 个查询，每个查询的描述如下：

• 1 L R x：对于 $i=L,L+1,\\dots,R$，将 $a_i$ 的值更新为 $\\displaystyle \\left\\lfloor \\frac{a_i}{x} \\right\\rfloor$。
• 2 L R y：对于 $i=L,L+1,\\dots,R$，将 $a_i$ 的值更新为 $y$。
• 3 L R：求解并打印 $\\displaystyle\\sum_{i=L}^R a_i$。

约束条件

• $1 \\leq N \\leq 5 \\times 10^5$
• $1 \\leq Q \\leq 10^5$
• $1 \\leq L \\leq R \\leq N$
• $1 \\leq a_i \\leq 10^5$
• $2 \\leq x \\leq 10^5$
• $1 \\leq y \\leq 10^5$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出，其中 $\\text{query}_i$ 表示要处理的第 $i$ 个查询：

$N$ $Q$ $a_1$ $a_2$ $\\dots$ $a_N$ $\\text{query}_1$ $\\text{query}_2$ $\\vdots$ $\\text{query}_Q$

每个查询可以采用以下三种格式之一：

$1$ $L$ $R$ $x$ $2$ $L$ $R$ $y$ $3$ $L$ $R$

输出

按照题目描述打印查询的答案，每个答案之间用换行符分隔。

示例输入1

3 5
2 5 6
3 1 3
1 2 3 2
3 1 2
2 1 2 3
3 1 3

示例输出1

13
4
9

初始时，$A = (2, 5, 6)$。因此，第一个查询的答案是 $a_1 + a_2 + a_3 = 2 + 5 + 6 = 13$。
处理完第二个查询后，$A = (2, 2, 3)$。因此，第三个查询的答案是 $a_1 + a_2 = 2 + 2 = 4$。
处理完第四个查询后，$A = (3, 3, 3)$。因此，第五个查询的答案是 $a_1 + a_2 + a_3 = 3 + 3 + 3 = 9$。

示例输入2

6 11
10 3 5 20 6 7
3 1 6
1 2 4 3
3 1 3
2 1 4 10
3 3 6
1 3 6 2
2 1 4 5
3 1 6
2 1 3 100
1 2 5 6
3 1 4

示例输出2

51
12
33
26
132