我喜欢查询问题

题目描述

给定 $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$。

输入格式

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

N Q
a_1 a_2 … a_N
query_1
query_2
⋮
query_Q

每个查询以以下三种格式之一给出：

1 L R x

2 L R y

3 L R

输出格式

对于每个 3 L R 查询，输出答案，每个答案占一行。

样例

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

13
4
9

初始时 $A = (2, 5, 6)$，因此第 1 个查询的答案是 $a_1 + a_2 + a_3 = 2 + 5 + 6 = 13$。

第 2 个查询处理完后，$A = (2, 2, 3)$，因此第 3 个查询的答案是 $a_1 + a_2 = 2 + 2 = 4$。

第 4 个查询处理完后，$A = (3, 3, 3)$，因此第 5 个查询的答案是 $a_1 + a_2 + a_3 = 3 + 3 + 3 = 9$。

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

51
12
33
26
132

数据范围

• $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$
• 输入中的所有值均为整数。