题目描述

在一个智慧农场里，有 $N$ 块农田，每块农田的作物产量（单位：吨）被记录在数组 $A = (a_1, a_2, \dots, a_N)$ 中。农场的管理员可以执行 $Q$ 条指令，来调整产量或者进行查询。

每条指令有三种可能的类型：

1. 收成优化 1 L R x

   • 选择第 $L$ 块到第 $R$ 块农田（包含端点）。
   • 对于每块选中的农田，其产量 $a_i$ 变为 $⌊ x / a_i ⌋$（即用 $x$ 整除 $a_i$ 的结果）。

2. 重新种植 2 L R y

   • 选择第 $L$ 块到第 $R$ 块农田（包含端点）。
   • 将这些农田的产量全部设为 $y$。

3. 统计产量 3 L R

   • 计算并输出第 $L$ 块到第 $R$ 块农田的总产量。

输入格式：

输入由标准输入提供，格式如下：

• 第一行包含两个整数 $N$（农田块数）和 $Q$（操作数）。

• 第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，代表初始的农田产量。

• 接下来的 $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

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：

• 初始状态： $A = (2, 5, 6)$
• 第 1 条指令： 3 1 3 计算区间 (1,3) 总产量 $2+5+6=13$。
• 第 2 条指令： 1 2 3 2 更新 $a_2$ 和 $a_3$，使得：
  • $a_2 = ⌊ 2 / 5 ⌋ = 2$
  • $a_3 = ⌊ 2 / 6 ⌋ = 3$
  • 新状态：$A = (2,2,3)$
• 第 3 条指令： 3 1 2 计算区间 (1,2) 总产量 $2+2=4$。
• 第 4 条指令： 2 1 2 3 使得 $a_1 = a_2 = 3$，即 $A = (3,3,3)$。
• 第 5 条指令： 3 1 3 计算区间 (1,3) 总产量 $3+3+3=9$。

数据范围

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