P15832 [JOI Open 2015] 消毒喷雾 / Sterilizing Spray

JOI 先生就职于 IOI 制药株式会社。在这家公司，研究人员正忙于开发新型杀菌喷雾的实验工作。 在这家公司，杀菌喷雾的**强度**定义如下：当我们对含有 $y$ 个细菌的培养皿使用一次强度为 $x$ 的喷雾后，该培养皿上的细菌数量变为 $\lfloor y/x \rfloor$，即 $y/x$ 向下取整得到的整数。现在，一种强度为 $K$ 的新型喷雾被研发出来。为了测试这种喷雾的性能，他们计划进行实验。实验中使用 $N$ 个编号为 $1, \dots, N$ 的培养皿。最初，培养皿 $i$ 上有 $C_i$ 个细菌。在实验中，他们将依次执行 $Q$ 个操作。每个操作是以下类型之一： - **操作 1**：选择一个培养皿 $a$ 和一个整数 $b$，调整培养皿 $a$ 上的细菌数量。此操作后，培养皿 $a$ 上的细菌数量变为 $b$。 - **操作 2**：选择两个满足 $1 \leq l \leq r \leq N$ 的整数 $l, r$。对编号为 $l, l+1, \dots, r-1, r$ 的每个培养皿各使用一次喷雾。 - **操作 3**：选择两个满足 $1 \leq l \leq r \leq N$ 的整数 $l, r$。计算编号为 $l, l+1, \dots, r-1, r$ 的培养皿上细菌数量的总和，并记录下来。 JOI 先生对在新型喷雾按预期工作的情况下，实验的结果感到好奇。鉴于你是一位优秀的程序员，他请你预测实验的结果。 请编写一个程序，确定实验中所有操作 3 所记录下来的数值。 ### 任务 给定喷雾的强度以及实验中的操作信息，编写一个程序确定所有操作 3 所记录下来的数值。

从标准输入读取以下数据。 - 输入的第一行包含三个以空格分隔的整数 $N, Q, K$。这表示喷雾的强度为 $K$，培养皿的数量为 $N$，实验中的操作次数为 $Q$。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含一个整数 $C_i$。这表示实验开始时培养皿 $i$ 上有 $C_i$ 个细菌。 - 接下来的 $Q$ 行中，第 $i$ 行（$1 \leq i \leq Q$）包含三个以空格分隔的整数 $S_i, T_i, U_i$。它们表示实验中第 $i$ 个操作的信息。 - 当 $S_i = 1$ 时，表示这是一个操作 1，其中 $a = T_i$，$b = U_i$。 - 当 $S_i = 2$ 时，表示这是一个操作 2，其中 $l = T_i$，$r = U_i$。 - 当 $S_i = 3$ 时，表示这是一个操作 3，其中 $l = T_i$，$r = U_i$。

输出实验中所有操作 3 所记录下来的数值。输出的行数等于实验中被执行的操作 3 的次数。

### 样例 1 解释 - 实验开始时，各培养皿上的细菌数量为 $1\ 2\ 8\ 1\ 3$。 - 将培养皿 2 上的细菌数量调整为 5。此操作后，细菌数量为 $1\ 5\ 8\ 1\ 3$。 - 对培养皿 3、4、5 各使用一次喷雾，即细菌数量除以 3 后向下取整。此操作后，细菌数量为 $1\ 5\ 2\ 0\ 1$。 - 计算培养皿 2、3、4、5 的细菌数量之和为 8，向输出写入 8。 - 对培养皿 1、2、3、4 各使用一次喷雾。此操作后，细菌数量为 $0\ 1\ 0\ 0\ 1$。 - 将培养皿 3 上的细菌数量调整为 2。此操作后，细菌数量为 $0\ 1\ 2\ 0\ 1$。 - 计算培养皿 3、4、5 的细菌数量之和为 3，向输出写入 3。 - 将培养皿 2 上的细菌数量调整为 4。此操作后，细菌数量为 $0\ 4\ 2\ 0\ 1$。 - 对培养皿 1、2 各使用一次喷雾。此操作后，细菌数量为 $0\ 1\ 2\ 0\ 1$。 - 将培养皿 1 上的细菌数量调整为 4。此操作后，细菌数量为 $4\ 1\ 2\ 0\ 1$。 - 计算培养皿 1、2、3、4、5 的细菌数量之和为 8，向输出写入 8。 ### 约束条件 所有输入数据满足以下条件。 - $1 \leq N \leq 100\,000$。 - $1 \leq Q \leq 100\,000$。 - $1 \leq K \leq 10$。 - $0 \leq C_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。 - $1 \leq S_i \leq 3$（$1 \leq i \leq Q$）。 - 当 $S_i = 1$ 时，满足 $1 \leq T_i \leq N$ 且 $0 \leq U_i \leq 1\,000\,000\,000$（$1 \leq i \leq Q$）。 - 当 $S_i = 2,3$ 时，满足 $1 \leq T_i \leq U_i \leq N$（$1 \leq i \leq Q$）。 ### 子任务 #### 子任务 1 [5 分] - $1 \leq N \leq 3\,000$。 - $1 \leq Q \leq 3\,000$。 #### 子任务 2 [10 分] - $K = 1$。 #### 子任务 3 [10 分] - $C_i \leq 1$（$1 \leq i \leq N$）。 - 当 $S_i = 1$ 时，满足 $U_i \leq 1$（$1 \leq i \leq Q$）。 #### 子任务 4-10 [75 分] - 无额外约束。 翻译由 DeepSeek V3.2 完成