说明

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 的次数。

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

8
3
8

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

174
444
76
23
41

提示

样例 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 完成